Введение, История - Генетический алгоритм

Генетимческий алгоримтм (англ.Genetic algorithm ) -- это эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путем случайного подбора, комбинирования и вариации искомых параметров с использованием механизмов, напоминающих биологическуюэволюцию. Является разновидностью эволюционных вычислений. Отличительной особенностью генетического алгоритма является акцент на использование оператора "скрещивания", который производит операцию рекомбинации решений-кандидатов, роль которой аналогична роли скрещивания в живой природе.

Генетический алгоритм популяция тривиальный

История

"Отцом-основателем" генетических алгоритмов считается Джон Холланд (en:John Henry Holland), книга которого "Адаптация в естественных и искусственных системах" (1975)[1] является основополагающим трудом в этой области исследований. Ему же принадлежит Генетические алгоритмы.

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

Ежегодно в мире проводится несколько конференций по этой тематике, информацию о которых можно найти в Интернет по адресам:

Www. natural-selection. com/eps/

Mat. gsia. cmu. edu/Conferences/ .

Общую схему генетических алгоритмов проще всего понять, рассматривая задачи безусловной оптимизации

Max{ f (i) | i {0,1}n }.

Примерами служат задачи размещения, стандартизации, выполнимости и другие. Стандартный генетический алгоритм начинает свою работу с формирования начальной Популяции I 0 = {I 1 ,I 2, ...,Is } -- конечного набора допустимых решений задачи. Эти решения могут быть выбраны случайным образом или получены с помощью вероятностных жадных алгоритмов. Как мы увидим ниже, выбор начальной популяции не имеет значения для сходимости процесса в асимптотике, однако формирование "хорошей" начальной популяции (например из множества локальных оптимумов) может заметно сократить время достижения глобального оптимума.

На каждом шаге эволюции с помощью вероятностного оператора СелекцииВыбираются два решения, родители I 1, I 2. Оператор Скрещивания По решениям I 1, I2 строит новое решение I' , которое затем подвергается небольшим случайным модификациям, которые принято называть Мутациями . Затем решение добавляется в популяцию, а решение с наименьшим значением целевой функции удаляется из популяции.

Доказательство теоремы схем.

1. Выбрать начальную популяцию I 0иположить

F* = max{F (I )| I I 0}, K : = 0.

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

Гипотеза 1.

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

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

Похожие статьи




Введение, История - Генетический алгоритм

Предыдущая | Следующая