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

1. Выбрать начальную популяцию I0 и положить
f* = max { f (i) | i I0}, k : = 0.

2. Пока не выполнен критерий остановки делать следующее.

2.1. Выбрать родителей i1, i2 из популяции Ik.
2.2. Построить i' по i1, i2.
2.3. Модифицировать i' .
2.4. Если f* < f (i' ), то f* : = f (i' ).
2.5. Обновить популяцию и положить k : = k+1.

Остановимся подробнее на основных операторах этого алгоритма: селекции, скрещивании и мутации. Среди операторов селекции наиболее распространенными являются два вероятностных оператора пропорциональной и турнирной селекции. При пропорциональной селекции вероятность на k-м шаге выбрать решение i в качестве одного из родителей задается формулой

в предположении, что f (i) > 0 для всех i Î I. При турнирной селекции формируется случайное подмножество из элементов популяции и среди них выбирается один элемент с наибольшим значением целевой функции. Турнирная селекция имеет определенные преимущества перед пропорциональной, так как не теряет своей избирательности, когда в ходе эволюции все элементы популяции становятся примерно равными по значению целевой функции. Операторы селекции строятся таким образом, чтобы с ненулевой вероятностью любой элемент популяции мог бы быть выбран в качестве одного из родителей. Более того, допускается ситуация, когда оба родителя представлены одним и тем же элементом популяции.

Как только два решения выбраны, к ним применяется вероятностный оператор скрещивания (crossover). Существует много различных версий этого оператора [15], среди которых простейшим, по видимому, является однородный оператор. По решениям i1, i2 он строит решение i' присваивая каждой координате этого вектора с вероятностью0,5 соответствующее значение одного из родителей. Если вектора i1, i2 совпадали скажем по первой координате, то вектор i' "унаследует" это значение. Геометрически, оператор скрещивания случайным образом выбирает в гиперкубе вершину i' , которая принадлежит минимальной грани, содержащей вершины i1, i2. Можно сказать, что оператор скрещивания старается выбрать новое решение i' где-то между i1, i2 полагаясь на удачу. Более аккуратная процедура могла бы выглядеть таким образом. Новым решением i' является оптимальное решение исходной задачи на соответствующей грани гиперкуба. Конечно, если расстояние Хемминга между i1, i2 равно n, то задача оптимального скрещивания совпадает с исходной. Тем не менее даже приближенное решение этой задачи вместо случайного выбора заметно улучшает работу генетического алгоритма [8, 9, 10, 14]. По аналогии с однородным оператором скрещивания легко предложить и другие операторы, использующие не только два, но и произвольное число решений из популяции. Например, в [20] использовалось восемь родителей. Другие примеры можно найти в [13]. С адаптацией этой идеи к задаче коммивояжера можно познакомиться в [17].

Оператор мутации, применяемый к решению i' в п. 2.3. генетического алгоритма, с заданной вероятностью pm Î (0, 1) меняет значение каждой координаты на противоположное. Например, вероятность того, что i' = (0, 0, 0, 0, 0) в ходе мутации перейдет в j' = (1, 1, 1, 0, 0), равна pm ´ pm ´ pm ´ (1 – pm) ´ (1 – pm) > 0. Таким образом, с ненулевой вероятностью решение i' может перейти в любое другое решение. Отметим, что модификация решения i' может состоять не только в случайной мутации, но и в частичной перестройке решения алгоритмами локального поиска. Применение локального спуска позволяет генетическому алгоритму сосредоточиться только на локальных оптимумах. Множество локальных оптимумов может оказаться экспоненциально большим и на первый взгляд кажется, что такой вариант алгоритма не будет иметь больших преимуществ. Однако экспериментальные исследования распределения локальных оптимумов свидетельствуют о высокой концентрации их в непосредственной близости от глобального оптимума [11, 18]. Это наблюдение известно как гипотеза о существовании "большой долины" для задач на минимум или "центрального горного массива" для задач на максимум.

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

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

 

 

45. Нейронный слой Кохонена. Кластеризация.

 

http://ru.wikipedia.org/wiki/%D0%9D%D0%B5%D0%B9%D1%80%D0%BE%D0%BD%D0%BD%D0%B0%D1%8F_%D1%81%D0%B5%D1%82%D1%8C_%D0%9A%D0%BE%D1%85%D0%BE%D0%BD%D0%B5%D0%BD%D0%B0

 

http://habrahabr.ru/post/143668/

 

http://mechanoid.kiev.ua/neural-net-kohonen-clusterization.html