Генетический алгоритм и его сущность

Содержание.

Введение…………………………………………………………………..2

Описание Генетического Алгоритма……………………………………3

Результаты тестирования………………………………………………...6

Заключение………………………………………………………………11

Список литературы………………………………………………………13

Приложение………………………………………………………………14

Введение.

В наше время перед человечеством каждый день возникает огромное множество проблем. И человечество нашло большое количество разных способов их решения. Одним из способов оптимизации, который хорошо себя зарекомендовал, является Эволюционный Алгоритм, и как его частный случай Генетический Алгоритм. Этот алгоритм основан на принципах биологической эволюции. Он способен отыскивать решения практически при полном отсутствии предположений о характере исследуемой функции.На сегодняшний день генетические алгоритмы доказали свою конкурентноспособность при решении многих NP-трудных задач и особенно в практических приложениях, где математические модели имеют сложную структуру и применение стандартных методов динамического или линейного программирования крайне затруднено.

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

Меня очень заинтересовали генетические алгоритмы, т.к. ранее я не встречалась с алгоритмами решающими практически любую оптимизационную задачу. Целью моей работы было рассмотреть различные модификации алгоритма на тестовых функциях и проанализировать, при какой модификации алгоритм для всех тестовых функций показывает хорошие результаты.

Описание Генетического Алгоритма.

Генетический алгоритм- это метод поиска решений практически любой оптимизационной задачи, моделирующий процессы природной эволюции.

Генетический алгоритм состоит из нескольких этапов:

1. Инициализация

2. Выращивание

3. Оценивание

4. Селекция

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

6. Мутация

Рассмотрим каждый из этих этапов подробно.

На первом этапе (Инициализация ) случайным образом выбирается первоначальная популяция хромосом (генотипов). Хромосома состоит из генов, которые задаются в бинарном виде, и это является отличительной чертой генетических алгоритмов. Прежде чем проводить Инициализацию, требуется посчитать длину хромосом (количество генов), которые будут использоваться. Длина зависит от количества переменных и области допустимых значений.

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

Следующий этап это Оценивание . Он подразумевает вычисление значений функции пригодности индивидов (качества решений-кандидатов).

Селекция - во время этого шага выбираются особи из текущей популяции и заносятся в популяцию родителей, из которых в свою очередь отбирается пара индивидов, которые, в конце концов, будут скрещиваться (важно заметить, что всё это происходит случайным образом). Для имитации естественной селекции индивиды с более высокой пригодностью должны выбираться с большей вероятностью. Существует большое число различных видов селекции.

a) Турнирная селекция . Для отбора индивида создается группа из N (N ³ 2) индивидов, выбранных случайным образом. Индивид с наибольшей пригодностью в группе отбирается, остальные - отбрасываются (турнир). N - размертурнира. Преимущества турнирной селекции заключаются в том, что нет преждевременной сходимости, нет стагнации, не требуется явное вычисление функции пригодности. Более того турнирная селекция имеет глубокие аналоги в биологии.

b) Пропорциональная селекция . Пропорциональная селекция работает приблизительно следующим образом: складываются значения пригодности всех индивидов, получается f , затем для каждого индивида значение его пригодности делитсяна f и получается доля этого индивида, которая переводится в проценты, а потом каждому индивиду отводится один из последовательных интервалов, размер которого пропорционален его пригодности. После всего этого случайным образом выбирается число, лежащее в одном из интервалов. Преимущества такой селекции то, что у лучших индивидов больше шансов быть отобранными, но в тоже время шанс остается и у худших индивидов. Но, тем не менее, у пропорциональной селекции есть и недостатки, такие как преждевременная сходимость и стагнация.

Пятый этап называется Скрещивание . Оно также бывает нескольких видов.

a) При Одноточечном скрещивании случайным образом выбирается точка разрыва родительской хромосомы, затем в одного

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать