Оптимизация на основе эволюционных вычислений. Генетические алгоритмы

Готовая работа

Реферат по курсу «Методы оптимизации и исследования операций»

на тему: «Оптимизация на основе эволюционных вычислений. Генетические алгоритмы»

Оглавление

1. Введение. 3

2. Естественный отбор в природе и генетическое наследование. 3

3. История развития эволюционных вычислений и их типы. 5

4. Идея генетического алгоритма. 7

5. Основное содержание генетического поиска. 7

5.1. Преимущества генетических алгоритмов. 8

5.2. Работа генетического алгоритма. 10

6. Эффективность применения генетических алгоритмов и пути ее повышения. 13

6.1 Показатели эффективности работы генетического алгоритма. 13

6.2 Распараллеливание как способ повышения эффективности работы генетического алгоритма  13

6.3. Влияние операторов генетического алгоритма на показатели его эффективности  14

6.4. Работы по совершенствованию генетического алгоритма. 16

7. Применение генетических алгоритмов и направления развития. 17

7.1. Обзор конкретных оптимизационных задач, решаемых генетическими алгоритмами  18

7.2. Направления развития генетических алгоритмов. 21

7.3. Демонстрация эффективности использования ГА для поиска максимума одномерной функции. 23

8. Выводы. 25

9. Список использованной литературы.. 25

 

1. Введение

По своей сути процессы адаптации являются оптимизационными процессами…

(Дж. Холланд)

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

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

Природа поражает своей сложностью и богатством проявлений. Среди примеров можно назвать сложные социальные системы, иммунные и нейронные системы, сложные взаимосвязи между видами. Они – всего лишь некоторые из чудес, ставшие очевидными при глубоком исследовании природы вокруг нас. Наука – это одна из систем, которая объясняет окружающее и помогает приспособиться к новой информации, получаемой из внешней среды. Многое из того, что мы видим и наблюдаем, можно объяснить теорией эволюции через наследственность, изменение (мутации) и отбор.

2. Естественный отбор в природе и генетическое наследование

Рассмотрим один из эффективных методов решения задач оптимизации, в котором объектом для подражания будет не нейрон и даже не какая-либо часть отдельного живого организма, а весь процесс развития жизни на Земле в целом.

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

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

Согласно эволюционной теории, каждый биологический вид целенаправленно развивается и изменяется для того, чтобы наилучшим образом приспособиться к окружающей среде. Можно сказать, что эволюция – это процесс оптимизации всех живых организмов. Рассмотрим, какими же средствами природа решает эту задачу оптимизации. ►

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

Основной закон генетического наследования интуитивно понятен – он состоит в том, что потомки похожи на родителей. В частности, потомки более приспособленных родителей будут, скорее всего, одними из наиболее приспособленных в своем поколении. Эта похожесть основана на совмещении хромосом ДНК отца и матери в ДНК ребёнка. ► В половых клетках хромосом только 23 (тогда как в любых других 46), и они непарные. При оплодотворении происходит слияние мужской и женской половых клеток и образуется клетка зародыша, содержащая как раз 46 хромосом. Какие свойства потомок получит от отца, а какие – от матери, зависит от того, какие именно половые клетки участвовали в оплодотворении. Дело в том, что процесс выработки половых клеток (так называемый мейоз) в организме подвержен случайностям, благодаря которым потомки все же во многом отличаются от своих родителей. При мейозе, в частности, происходит следующее: парные хромосомы соматической клетки сближаются вплотную, затем их нити ДНК разрываются в нескольких случайных местах и хромосомы обмениваются своими частями. Этот процесс обеспечивает появление новых вариантов хромосом и носит название «кроссинговер». Каждая из вновь появившихся хромосом окажется затем внутри одной из половых клеток, и ее генетическая информация может реализоваться в потомках данной особи.

Детали:

Тип работы: Реферат

Предмет: Компьютерные науки

Год написания: 2011

Страниц: 41

Литературы: 3 шт.

Есть: картинки, таблицы

Цена: 767 руб. (можно купить часть работы)

Добавить комментарий

Ваш email не будет показан.

Получать новые комментарии по электронной почте. Вы можете подписаться без комментирования.