Алгоритм слежения за целью.

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

В этом алгоритме в качестве значений весовой функции для ячейки С_i на этапе распространения волны используется выражение:

(1)

Таким образом, распространение волны происходит из тех ячеек очередного фронта, которые ближе расположены к ячейке цели В. При этом, очевидно, сокращается зона поиска, однако из-за приближённого вычисления нижней оценки для подмножества путей, ведущих из ячейки А в ячейку В через ячейку Сi, возможна потеря глобального минимума.

Проведение пути с помощью алгоритма слежения за целью приведен на рисунке 4. Как видно из рисунка 4, количество просмотренных ячеек в последнем случае сократилось до 36.

Рисунок 4

Замечание. Распространение волны происходит от множества ячеек с min P_i, начиная с ячейки, которая получила эту оценку последней (первой).

 

17.Простой генетический алгоритм

 

 

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

Генерация выполняется случайным выбором аллеями каждого гена. Далее организуется циклический процесс смены поколений.

for (k =0; k <G; k++), for (j=0; j<N; j++)

{Выбор родительской пары хромосом}

Кроссовер, Мутации, Оценка F, Селекция

{Замена текущего поколения новым} G – число повторений внешнего цикла.

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

Выбор родителей

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

(1)

Пр. Пусть F треб. min-т., тогда Р_i выбора родителя с хромосомой C_i вычисляется:

F_max – наихудшее значения F среди экземпляров текущего поколения.

F_i –значения функции i-ого экземпляра. (1) называется Правило колеса рулетки.

i
Fi
Fmax – Fi
Рi	0,5		0,1	0,4

Если в колесе рулетки выделены секторы пропорциональные (F_max – F_i), то вероятность попадания в них – суть F_i, определяется в соответствии с (1)

Пр. Пусть N = 4

F_i и Р_i в таблице:

Скрещивание

Хромоссомы	Гены
А	f	a	c	d	g	k	v	e
В	a	b	c	d	e	f	g	h
С	f	a	c	d	g	f	g	h
D	a	b	c	d	e	k	v	e

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

Операция мутации выполняется с вероятностью Р(). Происходит замена аллели значением, выбираемым с равной вероятностью с области определенного гена. Благодаря мутации расширяется область ген. поиска.

Селекция После каждого акта генерации пара потомков в новое поколение включается лучший экземпляр пары. Внутренний цикл простого г.а заканчивается, когда число экземпляров нового поколения станет N. Количество повторений G внешнего цикла, чаще всего определяется автоматически, по выявлению признаков вырождения (стагнации), но с условием не превышения лимита маш. t.

⇐ Предыдущая3456789101112Следующая ⇒

Поделиться:

Воспользуйтесь поиском по сайту: