Выживает самый приспособленный: естественный отбор алгоритмов

Date: 2015-10-07; view: 531.

Автор: Брайен Конноли

В статье рассматриваются:

определение генетического программирования;

выведение новых поколений алгоритмов;

перекрестная передача «хромосом» (скрещивание);

мутации;

повышение приспособленности.

Генетическое программирование (genetic programming, GP) — одна из самых удобных и универсальных методик решения задач, встающих перед разработчиками. Оно применяется для решения широкого круга проблем: символьной регрессии (symbolic regression), анализа данных (data mining), оптимизации и исследования поведения появляющегося потомства (emergent behavior) в биологических сообществах.

GP относится к классу технологий, называемых эволюционными алгоритмами. Эволюционные алгоритмы основаны на понятиях, используемых при изучении естественного отбора и эволюции. Живые существа чрезвычайно сложны — куда сложнее даже самых совершенных систем, разработанных человеком. При решении проблем с помощью эволюционных алгоритмов вместо явного проектирования и анализа применяют методику, аналогичную естественному отбору.

Эволюционный алгоритм решает проблему, генерируя массу случайных программ — вариантов решения проблемы. Каждый вариант запускается и оценивается согласно критериям приспособленности, заданным разработчиком. Эволюционный алгоритм выбирает из каждого поколения лучшие варианты решения и получает от них потомство, что аналогично естественному отбору в природе, являющемуся двигателем эволюции.

Генетическое программирование и генетические алгоритмы — два разных вида эволюционных алгоритмов. В генетических алгоритмах используются кодированные строки, представляющие конкретные решения проблемы. Эти строки обрабатываются программой моделирования (simulator), и лучшие из них смешиваются, образуя новое поколение. В генетическом программировании, о котором идет речь в статье, применяется другой подход. Здесь в селекции участвуют не кодированные представления решений, а исполняемые компьютерные программы.

Я рассмотрю простую GP-проблему, взятую из книги Джона Коза (John Koza) «Genetic Programming: On the Programming of Computers by Means of Natural Selection» (MIT Press, 1992); там, кстати, полно интересных идей. Задача состоит в том, чтобы создать искусственного муравья, наиболее эффективно проходящего сетку. По этой сетке пролегает извилистая дорожка, на которой находится пища. Цель — вывести муравья, способного собрать максимальное количество пищи за минимальное число ходов (steps).

Я разработал UI, который показывает сетку, рассматриваемую в задаче, и позволяет управлять работой GP-алгоритма. С помощью этого UI можно изучать, как создаются следующие друг за другом поколения муравьев, а также исследовать любого муравья из любого поколения и посмотреть сгенерированный для него C#-код и путь, который этот муравей проходит по сетке.

С базовым классом, представляющим проблему, работает внутренний процесс. В данном случае я создал базовый класс Ant, который реализует основные операции муравья и его состояние. Чтобы выводить новые подклассы класса, описывающего проблему, применяется GP-алгоритм. Этот алгоритм с помощью объектной модели документа исходного кода (CodeDOM) генерирует подкласс и метод Execute, представляющий одну из возможных стратегий поведения муравья.

Реализация универсальна в том смысле, что полностью основана на классе — эталоне проблемы (базовом классе Ant). Разработчик может задать новую GP-проблему, смоделированную с помощью класса Ant. Например, это может быть класс, представляющий допустимые функции для проблемы символьной регрессии. Поскольку во внутренней GP-обработке не используется логика, специфичная для муравья, та же архитектура применима и для решения проблемы символьной регрессии.

Я разработал эту реализацию, чтобы продемонстрировать, что в Microsoft .NET Framework есть все средства, необходимые для генетического программирования. Она отвечает всем требованиям, предъявляемым к генетическому программированию, и даже в своем нынешнем состоянии допускает дальнейшее расширение и усовершенствование. Например, с помощью сложных методик селекции, мутации и отсечения можно исследовать пространство решений гораздо глубже, чем в этом простом примере. Но поскольку эти методики — фактически лишь математические расширения базового алгоритма, статья показывает, что реализации GP на основе .NET могут достичь и такого уровня совершенства.

Я опишу GP-проблему, которую мы будем решать, и рассмотрю отношения между классами и основной код реализации. Кроме того, приведу обзор генетического программирования и покажу, как вывести муравьев, способных проходить более сложные пути, и как изменить класс, представляющий проблему, сделав доступными новые операции.

Пример проблемы

Абстрактная задача, которую я рассмотрю, — разработка интеллектуальной стратегии поведения простого искусственного муравья. Муравей перемещается по сетке 32 32, причем, если он выходит из сетки с одной стороны, то возвращается с другой. На сетке имеется вьющаяся дорожка, на которой находится пища. Дорожка начинается в ячейке [0,0]; из нее и выходит муравей. Каждая ячейка на пути может быть пустой, с пищей или с индикатором, который указывает, что данная ячейка является промежутком между областями, где есть пища. Дорожка должна быть непрерывной, начиная с исходной ячейки. Ячейка с пищей должна быть смежной минимум с одной ячейкой, которая тоже содержит пищу или помечена как промежуточная.

У простого муравья два элемента, полностью описывающие его состояние. Первый — текущая позиция муравья в сетке. Второй — направление, в котором он смотрит: влево, вправо, вверх или вниз. Муравей может делать три вещи: повернуть налево, повернуть направо или перейти в квадрат, на который он смотрит. У него лишь одно средство восприятия окружающей среды — функция FacingFood, сообщающая, есть ли пища в квадрате, на который смотрит муравей.

Когда муравей перемещается в квадрат с пищей, она удаляется из сетки, а общий объем пищи, собранный муравьем, увеличивается на 1. Когда муравей поворачивается или передвигается, счетчик ходов, потребовавшихся на сбор пищи, тоже увеличивается на 1.

Задача в том, чтобы создать муравья, способного на осмысленную последовательность поворотов и переходов в соответствии со значениями функции FacingFood. Например, такой последовательностью может быть:

Такой алгоритм отлично подходит для дорожек с пищей, которые всегда поворачивают вправо. Но нам нужно, используя GP, создать программу, которая наиболее эффективно проходит произвольные дорожки, содержащие пищу и прогалы.

UI приложения

На рис. 1 показан UI для .NET-реализации искусственного муравья. Панель сетки представляет собой матрицу 32 32 квадрата, на которой рисуется дорожка с пищей. Алгоритм работает с этой матрицей. При запуске загружается дорожка по умолчанию. Щелчок кнопки Empty Grid удаляет дорожку. Переключатели Food и Gap позволяют рисовать новую дорожку, щелкая сетку. Кнопка Save Grid выводит текущую дорожку в XML-файл. В дальнейшем дорожку можно загрузить из файла, щелкнув кнопку Restore Grid.

Рис. 1. Окно приложения «искусственный муравей»

Поля слева управляют работой GP-алгоритма. Вот что они собой представляют.

Generations. Алгоритм завершает работу после того, как сгенерировано указанное в этом поле число поколений. Однако, если удалось вывести идеального муравья (собирающего максимум пищи за минимум ходов), алгоритм немедленно прекращает работу.

Population. Это число муравьев в каждом поколении. Популяция представляет собой смесь наиболее эффективных муравьев из предыдущего поколения и их потомства.

Max Tree Depth. Сначала алгоритм генерирует муравьев случайным образом. Этот параметр задает, насколько глубокими могут быть начальные деревья выражений (expression trees) для муравьев.

Food Goal и Step Goal. Хотелось бы вывести муравья, который соберет объем пищи, заданный в поле Food Goal, за число ходов, указанное в поле Step Goal. Однако при вычислении значения Step Goal не учитываются повороты, необходимые муравью, когда дорожка меняет направление.

Чтобы посмотреть UI и приложение, выполним простой пример. Запустите приложение — его внешний вид показан на рис. 1. Ячейки с промежутками отделяют меньший квадрат с пищей в левом верхнем углу от более крупного квадрата, находящегося по соседству.

Эти два квадрата содержат 33 ячейки с пищей и два промежутка. Следовательно, минимальное число ходов для сбора всей пищи равно 35. Не забывайте, что в этом минимальном числе не учтены повороты, необходимые, когда муравей находится в углу квадрата.

Чтобы запустить процесс генетического программирования, оставьте в полях значения по умолчанию и щелкните кнопку Generate. Будет сгенерирована начальная популяция из 100 муравьев, каждый из которых следует случайной стратегии. Параметр Max Tree Depth равен 5, поэтому у муравьев начальной популяции дерево, содержащее операции выбора по условию, перехода и поворота, будет содержать максимум 5 уровней.

В списке под кнопкой Generate показываются сводные данные по каждому поколению: средняя «приспособленность» («fitness») каждого поколения и приспособленность лучшего и худшего муравьев. О том, что такое приспособленность, я расскажу позже. А пока достаточно знать, что чем выше приспособленность, тем лучше.

Когда будет сформировано десятое поколение, выберите сводные данные для Generation 1. В списке будут показаны все муравьи этого поколения. Каждый муравей представляется случайно сгенерированным классом. Для каждого муравья показываются имя, собранное количество пищи и число сделанных ими ходов. Имя класса муравья — GenX_AntY, где X — номер поколения, а Y — номер муравья в поколении. Лучший муравей поколения всегда показывается вверху списка. Выберите этого муравья в Generation 1.

Когда вы выбираете муравья, сведения о нем выводятся в текстовом поле под списком. Показываются родители муравья, т. е. сообщаются имена классов, по которым он был сгенерирован. Под списком родителей показывается код, созданный для выбранного муравья. В дальнейшем я расскажу о коде подробнее.

При выборе муравья активизируются две кнопки. Кнопка Replay Step дает возможность пользователю пошагово просмотреть путь, проделанный муравьем. По кнопке Replay All муравей автоматически воспроизводит весь путь. На рис. 2 показано, как выглядит UI после щелчка кнопки Replay All применительно к лучшему муравью из поколения 1. Сгенерированный код, «родословная» муравья и пройденный им путь — отличные средства изучения генетического алгоритма. Лучший муравей из поколения 1 собрал всего 18 единиц пищи за максимально допустимые 400 ходов. По его пути на рис. 2 видно, почему эффективность оказалась такой низкой. Заметьте: поскольку логика каждого муравья генерируется случайно, ваши результаты могут немного отличаться от моих.

Рис. 2. Низкая эффективность

Затем прокрутите список Generations к элементу Generation 10 и выберите лучшего муравья, находящегося вверху списка муравьев. Этот муравей получен селекцией и комбинированием наиболее эффективных муравьев из предыдущих поколений. Он собрал 33 кусочка пищи всего за 45 ходов. Его путь показан на рис. 3. Очевидно, что этот муравей использует стратегию, гораздо более удачную для данной дорожки.

Рис. 3. Путь муравья, сделавшего 45 ходов

Высокоуровневая архитектура классов

Высокоуровневая архитектура классов показана на рис. 4. Некоторые используемые мной классы, такие как Cell, AntTrailGrid, TerminationReport, IComparable, mFoodGathered и Ant, специфичны для конкретной проблемы. Если вы хотите применить ядро этой реализации для другой предметной области, вам придется разработать другие версии этих классов. Однако классы Generator, Function и ExpressionTree, образующие ядро GP-алгоритма, можно оставить фактически без изменений.

Класс Cell представляет ячейку сетки. Класс AntTrailGrid выполняет графические операции, отображающие панель сетки. Я не буду подробно описывать эти классы, так как они относятся скорее к пользовательскому интерфейсу, чем к генетическому программированию.

Класс Ant и связанный с ним класс TerminatingReport представляют проблему, которую я пытаюсь решить. Рис. 4. Архитектура классов

При инициализации класс Ant принимает сетку, количество пищи и максимально допустимое число ходов. В моей реализации для каждого муравья установлено ограничение в 400 ходов. У класса Ant имеются открытые методы поворота и перемещения и закрытые члены, в которые записываются число сделанных ходов и количество пищи, собранной при передвижении по сетке. Кроме того, в класс Ant входит член mTrail типа ArrayList, содержащий хронологию — информацию о том, в каких ячейках сетки побывал муравей. В класс также входит логическая функция FacingFood.

При каждом ходе класс проверяет, не собрал ли муравей всю пищу и не достигло ли число ходов максимально допустимого значения. Если одно из этих условий истинно, класс сохраняет хронологию в члене mConcludingReport типа TerminationReport. В TerminationReport записываются количества пищи и ходов и путь муравья. Метод Fitness класса TerminationReport измеряет приспособленность муравья. Он возвращает целое значение, вычисляемое по количеству собранной пищи и числу сделанных ходов. Муравьи, собравшие больше пищи за меньшее число ходов, приспособлены лучше, чем менее эффективные муравьи. Класс TerminationReport реализует метод CompareTo интерфейса IComparable. Метод CompareTo сравнивает экземпляры TerminationReport по приспособленности. После генерации очередного поколения класс Generator будет хранить в ArrayList сотни или даже тысячи экземпляров TerminationReport, и реализация IComparable позволит отсортировать элементы ArrayList по приспособленности.

Generator — ядро реализации GP. Он осуществляет селекцию, выведение потомства, генерацию кода, выполнение и сортировку результатов. При создании генератора конструктору передаются тип BaseClass (в данном случае класс Ant) и максимальная глубина дерева выражений. Применяя отражение (reflection) к типу BaseClass, генератор ищет его открытые методы, не принимающие параметров (кроме специального метода NotFinished). Все методы, не возвращающие значений, реализуют элементарные операции, используемые GP-алгоритмом. Все логические методы, не принимающие параметров, управляют выполнением элементарных операций. Информация об этих логических методах хранится в объектах Function. Когда метод NewGeneration вызывается для получения первоначальной популяции из N муравьев, этот метод генерирует N случайных объектов ExpressionTree. Generator использует эти объекты ExpressionTree и классы CodeDOM, чтобы сконструировать N подклассов класса Ant, у каждого из которых есть единственный метод Execute. В последнем содержится цикл, где операторы из дерева выражений выполняются, пока метод NotFinished возвращает true.

Generator помещает все эти классы в одно пространство имен, компилирует их в новую сборку и загружает ее. Затем создает по одному экземпляру каждого сгенерированного класса, вызывает его метод Execute и сохраняет TerminationReport. Реализация могла бы быть более надежной, если бы я изолировал каждую сборку в своем AppDomain, чтобы эту сборку можно было выгружать, когда она больше не нужна. Но в демонстрационных целях я предпочел не усложнять приложение и решил загружать все сборки в основной AppDomain.

У TerminationReport имеется статический метод GoalReport. Generator использует его для создания специального экземпляра класса TerminationReport. Этому экземпляру соответствует приспособленность идеального муравья, собравшего всю доступную пищу за минимальное число ходов. Генератор формирует одно поколение за другим, выполняя селекцию и скрещивание, пока число поколений не достигнет предела или пока не будет выведен идеальный муравей.

Generator — универсальная реализация GP. Как я утверждал выше, можно было бы определить другую проблему в виде «другого муравья». Так, этот муравей мог бы поддерживать набор элементарных математических операций — сложение, умножение и возведение в степень. Его сеткой был бы набор входных и выходных значений (x,y), возвращаемых функцией, для представления которой вам нужно получить математическое выражение. Для решения этой проблемы годится тот же класс Generator, фактически без изменений.

Чтобы архитектура действительно была универсальной, ее нужно модифицировать, но совсем чуть-чуть. Generator напрямую обращается к TerminationReport, чтобы сконструировать объект, соответствующий идеальному муравью, и использует некоторые знания о методе Init, который передает сетку создаваемому муравью. В дальнейшем я подробно рассмотрю Generator и расскажу, как сделать, чтобы он стал по-настоящему универсальным.

Генетическое программирование

В своей книге Джон Коза привел многочисленные примеры проблем, которые можно решить с помощью генетического программирования. Он разработал систематический подход, при котором конкретным проблемам сопоставляется канонический набор архитектурных решений, используемый разработчиком для моделирования проблемы.

В генетическом программировании используется набор объектов, которые Джон Коза назвал терминалами (terminals) и функциями. Муравьем управляют выражения поведения (behavior expressions) — древовидные структуры, состоящие из терминалов и функций. Терминалы — элементарные операции или литералы, которые нельзя разбить на подоперации. Функции — более высокоуровневые операции, использующие другие функции или терминалы. В нашем случае для искусственного муравья определены терминалы Left, Right и Move. Функцией в моем примере является логическая функция FacingFood, принимающая два аргумента терминала или функции. Выражение «if FacingFood, then Left, else Right» — пример выражения, содержащего функцию FacingFood и два потомка — терминалы Left и Right. Кроме того, я буду генерировать еще две функции. Первая, которую я назову P2, содержит две последовательные операции, которые также являются терминалами или функциями. Пример такой функции — выражение «Right;Move». Вторая функция, которую я добавлю, — функция P3. Она такая же, как P2, но содержит три подоперации. Пример P3 — выражение «Move; Right; if FacingFood then Right else Move».

Сначала GP-алгоритм генерирует популяцию случайных выражений. Один из параметров алгоритма — размер популяции, который входит в число параметров, задаваемых пользователем в UI. Затем выражения выполняются и оцениваются в соответствии с критериями приспособленности. Разработка критерия приспособленности — еще одна составляющая канонического GP. Мне хотелось бы получить эффективных муравьев, которые собирают много пищи за небольшое число ходов. Поэтому в критерии приспособленности должны учитываться количество собранной пищи и число сделанных ходов. В своей реализации я вычитаю число ходов из количества собранной пищи и добавляю 1000, чтобы величина приспособленности всегда была положительной. У муравья с более высокой приспособленностью больше шансов на выживание, чем у муравья с более низкой приспособленностью.

После начальной случайной генерации первого поколения начинается настоящая работа GP-алгоритма. Первый этап — селекция, при которой выбираются лучшие муравьи, копируемые в очередное поколение. Во многих реализациях GP используются сложные методики селекции, но в моей реализации ради простоты копируются 10% муравьев, лучших согласно нашему критерию приспособленности. Эти муравьи станут «родителями» муравьев следующего поколения.

В следующее поколение в первую очередь включается пул родителей, который копируется из предыдущего поколения. Поскольку это лишь 10% популяции, мне нужно заполнить остальные «вакансии». Для этого я беру родителей и, чтобы создать очередное поколение, получаю от них потомство. Выбираются пары родителей, и каждая пара родителей приносит пару потомков, каждый из которых сочетает элементы родителей. Родители выбираются согласно их приспособленности. Вообще говоря, у более приспособленных родителей больше шансов принести потомство.

Чтобы получить пару детей от пары родителей, применяется алгоритм «перекрестной передачи хромосом», или попросту скрещивания (рис. 5). В каждом родителе случайным образом выбирается точка обмена «хромосомами» (crossover point). Родители обмениваются своими поддеревьями, находящимися ниже точки обмена, в результате чего создаются два потомка.

Кроме того, в большинстве GP-алгоритмов реализуется мутация. Мутации — это случайные изменения небольшого числа потомков, направленные на внесение разнообразия в популяцию. Мутации необходимы, поскольку иначе в популяции будут полностью доминировать несколько удачных генотипов, что, начиная с определенного момента, препятствует дальнейшему прогрессу. В данной реализации, чтобы внести элемент случайности, при скрещивании выполняется простая мутация. В двух процентах случаев терминальный узел при копировании замещается случайно выбранным терминалом.

Рис. 5. Скрещивание

Vocabulary

A

1. abstract - абстрактный

2. according – согласный

3. adjacent – смежный

4. akin – аналогичный

5. algorithm - алгоритм

6. allow (v) – позволять

7. allowable – допустимый

8. always - всегда

9. amount – количество

10. analysis - анализ

11. ant – муравей

12. appear (v) – показываться

13. application – приложение

14. approach - подход

15. arbitrary – произвольный

16. article - статья

17. artificial – искусственный

18. assembly – сборка

19. augment (v) – расширять

20. available – доступный

21. average – средний

B

22. basic - базовый

23. behavior - поведение

24. beneath – внизу, ниже

25. between - между

26. bloodline – генотип

27. bool – логический

28. both – оба

29. branching – выбор

30. breed (v) – выводить, передавать

C

31. cell – ячейка

32. change (v) – менять, изменять

33. class - класс

34. clause – операция, пункт

35. clearly – очевидно

36. code - код

37. complex – сложный

38. community – сообщество

39. contain (v) – содержать, вмещать

40. conditional – условный

41. continuous – непрерывный

42. control (v) - управлять

43. core – ядро

44. сross breeding – скрещивание

45. crossover – скрещивание

46. current – текущий, нынешний

D

47. deal with (v) – рассматривать

48. default – базовый, по умолчанию

49. definition – определение

50. demonstrate (v) - демонстрировать

51. depth – мощность, полнота

52. describe (v) – описывать

53. developer - разработчик

54. direction – направление

55. display (v) - показывать

56. diversity – разнообразие

57. document - документ

58. drive (v) - основываться

E

59. efficiently – эффективно

60. emergent – появляющийся

61. empty – пустой

62. encoded – закодированный

63. environment – окружающая среда

64. entirely – полностью

65. essential – обязательный

66. evaluate (v) – оценивать

67. evolutionary - эволюционный

68. evolve (v) – развивать, получать

69. example - пример

70. execute (v) – запускаться, работать

71. explicit – явный

72. exponentiation – возведение в степень

73. expression – выражение

74. extraordinarily - чрезвычайно

F

75. face (v) – смотреть

76. fit - приспособленный

77. fitness - приспособленность

78. follow (v) – применять

79. food – пища

80. fully - полностью

81. function - функция

82. further - далее

G

83. gap – промежуток, пропуск

84. gather ( v) – собирать

85. general-purpose – универсальный

86. generation - поколение

87. genetic – генетический

88. give ( v) – привести, предоставить

89. grid - сетка

H

90. halt (v) – прекращать

91. hence - хотя

92. high -

I

93. immediately – немедленно

94. implement (v) – реализовать

95. improve (v) – совершенствовать

96. indicator - индикатор

97. increase (v) – повышать

98. increment (v) – увеличиваться на 1

99. initial – начальный

100. insight – понятие

101. instance - пример

102. instantiate – сконструировать

103. instead – вместо, на самом деле

104. intelligent – интеллектуальный

105. internal – внутренний

106. invoke (v) – вызывать

107. involve (v) – использовать(ся)

108. item – единица, штука

J

K

109. kernel – ядро

110. key - основной

L

111. least - минимальный

112. level - уровень

113. lineage – родословная

114. literal – литерал

115. logic - логика

116. loop – цикл

M

117. maintain (v) – содержать

118. mark (v) – маркировать, отмечать

119. master - эталон

120. measure (v) – измерять

121. member – элемент

122. metric – критерий

123. may (v) – быть в праве

124. mine (v) – анализ

125. mix (v) – смешивать(ся)

126. modeled – смоделированный

127. move (v) – двигать, перемещать(ся)

128. multiplication – умножение

129. mutation - мутация

N

130. natural - естественный

131. necessary – необходимый

132. new - новый

O

133. object - объектный

134. objective – цель

135. obtain (v) – добыть, собрать

136. offspring – потомок

137. operation - операция

138. optimization - оптимизация

139. origin – исходная точка

140. other - другой

141. otherwise – иначе

142. overview - обзор

P

143. pair – пара

144. particular – конкретный

145. perform (v) – исполнять

146. pertain (v) – принадлежать, относиться

147. plenty of room – много

148. point - ячейка

149. pool – пул (клеток, иммунология)

150. poor – низкое (качество)

151. position - позиция

152. possible – возможный

153. practical – практический, реальный

154. present – нынешний, настоящий

155. previous – предыдущий

156. prior – предыдущий

157. problem – проблема, задача

158. produce (v) – представлять, генерировать

159. pruning – отсечение

160. purpose - цель

Q

161. qualify (v) - предъявлять

R

162. random - случайный

163. rate (v) – оценивать

164. recall (v) – напоминать

165. record (v) – записывать

166. reflect (v) – учитывать

167. regression - регрессия

168. relationship – отношение, связь

169. remove (v) - удалять

170. representation - представление

171. retrieve (v) – работать

172. return (v) - возвращаться

173. requesting – запрос

174. requirement – требование

175. robust - надежный

S

176. same – тот же

177. sample – пример

178. scroll (v) – прокручивать

179. selection – отбор

180. seminal – плодотворный

181. sense – смысл

182. sensor – датчик, воспринимающее средство

183. series – последовательность

184. set – набор

185. several – некоторый

186. show (v) - показывать

187. side – сторона

188. simplicity – простота

189. simulator – программа моделирования

190. slightly – немного

191. slot – вакансия

192. solve (v) - решать

193. solution – решение

194. sophistication – совершенство

195. space - пространство

196. specify (v) – установить

197. square - квадрат

198. state – состояние

199. step - шаг

200. store (v) – храниться

201. string – строка

202. study (v) - изучать

203. subsequent – последующий

204. subtract (v) – вычитать

205. successive – последующий

206. survival – выживание

207. symbolic - символьный

208. swap (v) - обмениваться

T

209. technique – методика

210. thing - вещь

211. through - между

212. tool – средство, инструмент

213. total - общий

214. trail – дорожка

215. turn (v) - поворачивать

U

216. useful - удобный

V

217. vary (v) – отличаться

218. view (v) – посмотреть

219. void (method) – не возвращающий значение

W

220. walk (v) - проходить

221. weaving – извилистый

222. wide range – широкий круг

223. winding – извилистый

224. work (v) – работать

X

Y

225. yield (v) - приносить

Z