Автор работы: Пользователь скрыл имя, 16 Декабря 2013 в 13:49, курсовая работа
Природа всегда поражала человека своим совершенством и богатством всех своих проявлений. Это и сложные социальные системы, иммунные и нейронные системы, сложные взаимосвязи между видами. Многое из того, что мы видим и наблюдаем, можно объяснить с позиций теории эволюции через наследственность, изменчивость и отбор.
Теория эволюции, впервые представленная Чарльзом Дарвином в работе «Происхождение видов путём естественного отбора», оказала огромное влияние на мировоззрения людей.
Введение 3
Общие сведения 3
Актуальность 3
Обьект исследования 4
Предмет исследования 4
Цель работы 4
Задачи работы 5
Основная часть 5
1. История эволюционных вычислений 5
2. Естественный отбор в природе 5
Cредства Windows 71333. Основные понятия генетических алгоритмов 6
4. Общий вид генетического алгоритма 8
5. Пример 14
заключение 18
CПиСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ 19
Селекция хромосом заключается в выборе (по рассчитанным на втором этапе значениям функции приспособленности) тех хромосом, которые будут участвовать в создании потомков для следующей популяции, т.е. для очередного поколения. Такой выбор производится согласно принципу естественного отбора, по которому наибольшие шансы на участие в создании новых особей имеют хромосомы с наибольшими значениями функции приспособленности. Существуют различные методы селекции. Наиболее популярным считается так называемый метод рулетки (roulette wheel selection), который свое название получил по аналогии с известной азартной игрой. Каждой хромосоме может быть сопоставлен сектор колеса рулетки, величина которого устанавливается пропорциональной значению функции приспособленности данной хромосомы. Поэтому чем больше значение функции приспособленности, тем больше сектор на колесе рулетки. Все колесо рулетки соответствует сумме значений функции приспособленности всех хромосом рассматриваемой популяции. Каждой хромосоме, обозначаемой chi для i =1,2, ..., N (где N обозначает численность популяции) соответствует сектор колеса v(chi), выраженный в процентах согласно формуле:
Где,
причем F(chi) - значение функции приспособленности хромосомы chi, a ps(chi) -вероятность селекции хромосомы chi. Селекция хромосомы может быть представлена как результат поворота колеса рулетки, поскольку “выигравшая” (т.е. выбранная) хромосома относится к выпавшему сектору этого колеса. Очевидно, что чем больше сектор, тем больше вероятность “победы” соответствующей хромосомы. Поэтому вероятность выбора данной хромосомы оказывается пропорциональной значению ее функции приспособленности. Если всю окружность колеса рулетки представить в виде цифрового интервала [0, 100], то выбор хромосомы можно отождествить с выбором числа из интервала [а, b], где а и b обозначают соответственно начало и окончание фрагмента окружности, соответствующего этому сектору колеса; очевидно, что 0 ≤ а < b ≤ 100. В этом случае выбор с помощью колеса рулетки сводится к выбору числа из интервала [0, 100], которое соответствует конкретной точке на окружности колеса [1, с. 130].
При турнирной селекции формируется случайное подмножество из элементов популяции и среди них выбирается один элемент с наибольшим значением целевой функции. Турнирный отбор реализует n турниров, чтобы выбрать n особей. Каждый турнир построен на выборке k элементов из популяции, и выбора лучшей особи среди них. Наиболее распространен турнирный отбор с k=2.
Турнирная селекция имеет определенные преимущества перед методом рулетки, так как не теряет своей избирательности, когда в ходе эволюции все элементы популяции становятся примерно равными по значению целевой функции. Пропорциональный отбор не гарантирует сохранности лучших результатов, достигнутых в какой-либо популяции, и для преодоления такого явления используется элитный отбор - несколько лучших индивидуумов переходят в следующее поколение без изменений, не участвуя в кроссинговерe и отборе.
Операторы селекции строятся таким образом, чтобы с ненулевой вероятностью любой элемент популяции мог бы быть выбран в качестве одного из родителей. Более того, допускается ситуация, когда оба родителя представлены одним и тем же элементом популяции.
В любом
случае каждое следующее поколение
будет в среднем лучше
Отбор в генетическом алгоритме тесно связан с принципами естественного отбора в природе следующим образом:
Таблица
Приспособленность индивидуума |
Значение целевой функции на этом индивидууме. |
Выживание наиболее приспособленных |
Популяция следующего поколения формируется в соответствии с целевой функцией. Чем приспособленнее индивидуум, тем больше вероятность его участия в кроссовере, т.е. размножении. |
В результате процесса селекции создается родительская популяция, также называемая родительским пулом (mating pool) с численностью N, равной численности текущей популяции.
Применение генетических операторов к хромосомам, отобранным с помощью селекции, приводит к формированию новой популяции потомков от созданной на предыдущем шаге родительской популяции.
Скрещивание. Служит для создания следующей популяции на основе промежуточной при помощи операторов кроссинговера и мутации, которые имеют случайный характер. Каждому элементу промежуточной популяции, если надо подбирается партнёр и вновь созданная хромосома помещается в новую популяцию.
Оператор кроссинговера (в литературе по генетическим алгоритмам также употребляется название кроссовер или скрещивание) - операция, при которой две хромосомы обмениваются своими частями. Производит обмен генетического материала между родителями для получения потомков. Кроссинговер смешивает "генетический материал" двух родителей, причем можно ожидать, что приспособленность родителей выше средней в предыдущем поколении, так как они только что прошли очередной раунд борьбы за выживание. Это аналогично соперничеству настоящих живых существ, где лишь сильнейшим удается передать свои (предположительно хорошие) гены следующему поколению. Важно, что кроссинговер может порождать новые хромосомы, ранее не встречавшиеся в популяции. Простейший одноточечный кроссинговер (рис. 2) производит обмен частями, на которые хромосома разбивается точкой кроссинговера. Одноточечный кроссовер работает следующим образом. Сначала, случайным образом выбирается одна из l-1 точек разрыва. Точка разрыва - участок между соседними битами в строке. Обе родительские структуры разрываются на два сегмента по этой точке. Затем, соответствующие сегменты различных родителей склеиваются и получаются два генотипа потомков. Двухточечный кроссинговер обменивает кусок строки, попавшей между двумя точками. Предельным случаем является равномерный кроссинговер, в результате которого все биты хромосом обмениваются с некоторой вероятностью. Этот оператор служит для исследования новых областей пространства и улучшения существующих (приспособление).
Рис. 2. - Кроссинговер
Все типы кроссинговера обладают общим свойством: они контролируют баланс между дальнейшим использованием уже найденных хороших подобластей пространства и исследованием новых подобластей. Достигается это за счет неразрушения общих блоков внутри хромосом-родителей, сохраняющем "хорошие" паттерны, и одновременном исследовании новых областей в результате обмена частями строк (хромосом). Совместное использование отбора и кроссинговера приводит к тому, что области пространства, обладающие лучшей средней оптимальностью, содержат больше элементов популяции, чем другие. Таким образом, эволюция популяции направляется к областям, содержащим оптимум с большей вероятностью, чем другие[5].
Оператор мутации с вероятностью рт изменяет значение гена в хромосоме на любое другое возможное значение. Например, если в хромосоме [100110101010] мутации подвергается ген на позиции 7, то его значение, равное 1, изменяется на 0. что приводит к образованию хромосомы [100110001010]. Как уже упоминалось выше, вероятность мутации обычно очень мала, и именно от нее зависит, будет данный ген мутировать или нет. Вероятность рт мутации может эмулироваться, например, случайным выбором числа из интервала [0, 1] для каждого гена и отбором для выполнения этой операции тех генов, для которых разыгранное число оказывается меньшим или равным значению рт.
Рис. 3. - Мутация
Формирование новой популяции.
Хромосомы, полученные в результате применения генетических операторов к хромосомам временной родительской популяции, включаются в состав новой популяции. Она становится так называемой текущей популяцией для данной итерации генетического алгоритма. На каждой очередной итерации рассчитываются значения функции приспособленности для всех хромосом этой популяции, после чего проверяется условие остановки алгоритма и либо фиксируется результат в виде хромосомы с наибольшим значением функции приспособленности, либо осуществляется переход к следующему шагу генетического алгоритма, т.е. к селекции. В классическом генетическом алгоритме вся предшествующая популяция хромосом замещается новой популяцией потомков, имеющей ту же численность.
Выбор “наилучшей” хромосомы.
Если условие остановки
алгоритма выполнено, то следует
вывести результат работы, т.е. представить
искомое решение задачи. Лучшим решением
считается хромосома с
5. Пример
Рассмотрим очень простой пример - задачу нахождения максимума функции, заданной выражением f(х)=2х²+1 для целочисленной переменной x, принимающей значения от 0 до 31. Для применения генетического алгоритма необходимо, прежде всего, закодировать значения переменной x в виде двоичных последовательностей. Очевидно, что целые числа из интервала [0,31] можно представить последовательностями нулей и единиц, используя их представление в двоичной системе счисления. Число 0 при этом записывается как 00000, а число 31 - как 11111. В данном случае хромосомы приобретают вид двоичных последовательностей, состоящих из 5 битов, т.е. цепочками длиной 5.
Также очевидно, что в роли функции f(x) приспособленности будет выступать целевая функция, заданная выражением f(х)=2х²+1. Тогда приспособленность хромосомы chᵢ , i=1,2,…,N. будет определяться значением функции f(x) для x, равного фенотипу, соответствующему генотипу chᵢ. Обозначим эти фенотипы chᵢ*. В таком случае значение функции приспособленности хромосомы chᵢ (т.е.F(chᵢ) ) будет равно f(chᵢ*).
Выберем случайным образом исходную популяцию, состоящую из 6 кодовых последовательностей (например, можно 30 раз подбросить монету); при этом N=6. Допустим, что выбраны хромосомы
Соответствующие им фенотипы - это представленные ниже числа из интервала от 0 до 31:
Рассчитываем значения функции приспособленности для каждой хромосомы в популяции и получаем
Селекция хромосом. Методом рулетки, выбираем 6 хромосом для репродукции. Колесо рулетки представлено на рисунке
Допустим, что выбраны числа
97 26 54 13 31 88.
Это означает выбор хромосом
Ch₆ Ch₄ Ch₆ Ch₁ Ch₄ Ch₆
Пусть скрещивание выполняется с вероятностью pc=1. Допустим, что для скрещивания сформированы пары
Ch₁ и Ch₄ Ch₄ и Ch₆ Ch₆ и Ch₆
Кроме того, допустим, что
случайным образом выбрана
При условии, что вероятность мутации pm=0, в новую популяцию включаются хромосомы
Для расчета значений функции приспособленности этих хромосом необходимо декодировать представляющие их двоичные последовательности и получить соответствующие им фенотипы. Обозначим их chᵢ*. В результате декодирования получаем числа (из интервала от 0 до 31).
Соответственно, значения функции приспособленности хромосом новой популяции, рассчитанные по формуле f(х)=2х²+1, составят
Легко заметить, что в этом случае среднее значение приспособленности возросло с 589 до 1262. Обратим внимание, что если на следующей итерации будут сформированы для скрещивания пары хромосом, например,Ch₄ и Ch₂,Ch₅ и Ch₂ или Ch₆ и Ch₂ с точкой скрещивания 2 или 3, то среди прочих будет получена хромосома с фенотипом[11111], равным числу 31, при котором оптимизируемая функция достигает своего максимума. Значение функции приспособленности для этой хромосомы оказывается наибольшим и составляет 1923. Если такое сочетание пар в данной итерации не произойдет, то можно будет ожидать образования хромосомы с наибольшим значением функции приспособленности на следующих итерациях. Хромосома [11111] могла быть получена и на текущей итерации в случае формирования для скрещивания пары Ch₁ и Ch₆ с точкой скрещивания 3.
Отметим, что при длине хромосом, равной 5 битам, пространство поиска очень мало и насчитывает всего 2⁵=32 точки. Представленный пример имеет исключительно демонстрационный характер. Применение генетического алгоритма для такого простого примера практически нецелесообразно, поскольку его оптимальное решение может быть получено мгновенно. Однако этот пример пригоден для изучения функционирования генетического алгоритма. [2]
Заключение
В ходе работы были рассмотрены исторические сведения, основные понятия генетических алгоритмов, общий вид генетического алгоритма, генетические операторы. Также мы рассмотрели применение генетического алгоритма, на примере задачи нахождения максимума функции.
В завершении хотелось бы отметить, что область применения генетических алгоритмов многогранна.
Генетические алгоритмы в различных формах применяются ко многим научным и техническим проблемам. Генетические алгоритмы используются при создании других вычислительных структур, например, автоматов или сетей сортировки. В машинном обучении они используются при проектировании нейронных сетей или управлении роботами. Они также применяются при моделировании развития в различных предметных областях, включая биологические (экология, иммунология и популяционная генетика), социальный (такие как экономика и политические системы) и когнитивные системы.
Генетические алгоритмы
применяются для решения
СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ