Забыл написать по поводу выбора функции фитнеса... Если решается задача на минимум, т.е. f(x) -> min, то можно ввести т. о.:
 
где worst - самое плохое решение за всю эволюцию. 

Теперь по поводу скрещивания для перестановок. Пусть мы выбрали 2х родителей: p1=(a b c d e f g h i), p2=(f c b h e a g d i). Выбираем 2 случайные точки, которые поделят наши перестановки на 3 части:
a b . c d e f  . g h i
f  c . b h e a . g d i
И начинаем строить ребенка с конца. Последние 3 элемента берем от 2го родителя:
_ _._ _ _ _.g d i
Среднюю часть берем у 1го родителя. Если какой-то элемент уже есть в перестановке, то добавляем другой, отсутсвующий, с сохранением относительного порядка:
_ _.с _ _ _.g d i
_ _.с e _ _.g d i   // d уже есть, берем e
_ _.с e f _.g d i    // e уже есть, берем f
_ _.с e f h.g d i    // f уже есть, берем h
Первые элементы - от 2го:
b _.с e f h.g d i  // f уже есть, берем b
b a.с e f h.g d i  // c уже есть, берем a

Получили ребенка: (b a с e f h g d i). После этого подвергаем его мутации:
Вариант 1: выбираем 2 случайные позиции и инвертируем среднюю часть:
b.a с e.f h g d i
b.e с a.f h g d i
При этом изменяться 2 ребра
Вариант 2: выбираем 2 случайные позиции и меняем местами элементы в этих позициях
b a с e f h g d i
        ^         ^
b a с d f h g e i
Поменялись 4 ребра. Эта мутация более сильная.

Я вот задумался, а как, в случае бинарных хромосом обходятся с кодированием значений не равных двум в степени? Например, если у величины три возможных значения, то одним битом ее не закодируешь, а двухбитная кодировка даст четвертое значение (11) недопустимое для этой величины?

Все, что сам придумал - результаты мутаций дающие величину 11 признавать изначально дохлыми и мутировать заново. Но есть наверное какой-то более разумный подход?

_Y_, не совсем понял о чем речь... Если задача на бинарных векторах, то значенния генов либо 0, либо 1.  Если же хромосома представляет собой вектор вещественных чисел либо что-то другое, то и оператор мутации реализуется по другому

Joss, в книжке, которую я читал было что-то вроде такого: "первые два бита кодируют такое-то свойство, последующие четыре бита кодируют то-то, последующие..." ну и так далее. До векторов  вещественных чисел я не дочитал (пока, надеюсь). То есть, имеются какие-то свойства с конечным числом значений. Их значения кодируются не битами, а бинарными последовательностями. Вот и непонятно, как быть с моим вопросом в этом случае.

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


Это сообщение отредактировал(а) Joss - 8.1.2008, 19:03

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

Еще вопрос возник в ту же тему. Положим, у меня есть бинарная хромосома 
1000001000000000110000..........
При этом я заранее знаю, что число единиц в ней гораздо меньше, чем число нулей. Понятное дело, что хромосомы со слишком большим числом единиц отловятся функцией фитнеса. Но! При этом будет жраться немеряно времени на производство полудохлых потомков. Думаю, можно изначально задать разную вероятность мутаций 0->1 и 1->0, но не уверен в грамотности такого решения. А может есть что-то еще грамотнее?

Это сообщение отредактировал(а) _Y_ - 15.1.2008, 17:38

Дочитал книжку до конца. Пожалуй пятую главу рекомендовать можно - в ней описание подходов к выбору конкретных алгоритмов.

Это сообщение отредактировал(а) _Y_ - 17.1.2008, 18:05