| | | | | | | | | | | | | | | | | | | | | | | | Г | е | н | е | т | и | ч | е | с | к | о | е | | п | р | о | г | р | а | м | м | и | р | о | в | а | н | и | е | | | | | | | | | | | | | | | | | | | | | | | | | |
3.1.96 | |
Для решения многих задач существуют алгоритмы, дающие точное их решение. |
Однако существуют задачи, сложность которых не позволяет найти точного решения |
из-за невозможности человека предложить такой алгоритм. Такие сложные задачи |
кроме оптимального (самого лучшего) решения могут иметь множество других |
решений, более-менее подходящих или совсем неподходящих. |
Генетическое программирование основывается на модели эволюции. Алгоритм |
работает над популяцией индивидуумов, представленных "хромосомными наборами". |
Каждая такая "хромосома" представляет собой запись решения целевой задачи |
(обычно в двоичном алфавите, но можно использовать любой алфавит). Кроме |
популяции необходимо правило естественного отбора - правило определения |
"хорошести" того или иного решения задачи. На каждом этапе эволюции для каждой |
особи популяции определяется ее "жизненная сила" - хорошесть представляемого |
ею решения целевой задачи. |
Так же как и в природе не обойтись без скрещивания, мутации и вымирания. |
Скрещивание | представляет собой процесс создания особи (индивида) часть генома |
(хромосомного набора) которого принадлежит одной особи, часть другой и т.д. | В | |
отличие от природной эволюции, в скрещивании могут принимать участие более 2 | |
особей популяции | . | Мутация | представляет собой процесс случайного изменения |
хромосомного набора у определенного числа особей популяции. | Вымирание | - |
удаление определенного числа членов популяции пропорционально их возрасту и |
"жизненной" силы. |
|
Псевдоалгоритм выглядит следующим образом: |
|
t = 0 |
создать популяцию; |
подсчитать жизненную силу(t); |
while not done do |
t = t + 1 |
скрещивание(t); |
мутация(t); |
подсчет жизненной силы(t); |
вымирание(t); |
end while |
|
Алгоритм заканчивает работу когда один или несколько членов популяции |
достигают определенного заранее заданного уровня "жизненной силы" - т.е. мы |
получаем решение заранее заданного "качества". |
|
Генетический алгоритм очень хорошо решает многокритериальные переборные |
задачи, задачи линейного программирования и др. Скорость нахождения решения и |
нахождение глобального оптимума зависит от размера популяции, правила |
скрещивания, скорости размножения и мутации, зависимости вымирания от возраста |
и жизненной силы и т.п. |
|