9 лет прошло... )))

Ответить

Как правило, близость по Хэммингу и близость в еквлидовом пространстве не совпадают. Именно поэтому в свое время были попытки использовать кодирование Грея, чтобы "согласовать" оба пространства. Впрочем, эти попытки не принесли желаемого результата из-за того, что при этом пространство поиска "перетасовывается" совершенно непредсказуемым образом. Применение генетических операторов к закодированным по Грею хромосомам часто приводит к хаотическим перемещениям по пространству генотипов и мало напоминает направленный поиск, ради которого все мы так стараемся. Но это уже отступление от темы, просто, дополнительное объяснение для студентов, интересующихся ГА, и, вполне возможно, набредших на этот форум.

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

> В случае отсутвия закономерностей (как например, отсутвует закономерность
> между номером паспорта и цветом глаз) последовательный перебор лучше
> только тем, что не допускает повторной проверки ранее рассмотренных
> генотипов. Да - это долго, но и ГА также будет либо долго работать, либо
> получит плохое решение.

Не очевидное утверждение, потому что слишком общее. И, по Вашему, получается, что при отсутствии закономерностей между параметрами лучше последовательный перебор, а если закономерности есть, то, выходит, что ГА тут бессилен из-за того, что в нем слишком простые операторы? А как же тогда получилось, что куча народу использовало ГА и весьма успешно, решив при этом не меньшую кучу задач? ;)

Информация к размышлению о простоте операторов. При гетерозиготном биологическом скрещивании обмен хромосомной информацией осуществляется с использованием операции перекреста (кстати, это "правильный" биологический перевод термина crossover, но сейчас уже поздно что-либо менять), аналогичной одноточечному кроссоверу (!) в ГА. И в случае с природой все неплохо работает...

Недостатки генетических операторов, если эти недостатки имеются, не в том, что они "просты" (кстати, напишите, пожалуйста, что Вы имеете в виду под простотой), а в том, как они осуществляют отображение (mapping) в пространстве генотипов. Если с помощью генетических операторов возможно попасть в любую точку пространства путем целенаправленного поэтапного изменения хромосом в текущей популяции, то плохи они могут быть только тем, что переход будет происходить слишком долго. Кстати, W. Spears давал некоторый оценки времени перехода (transition time) к равновесному распределению и равновесию Роббинса.

И еще. На мой взгляд, есть некоторая доля лукавства в том, что говоря о простоте генетических операторов, одновременно предпалагается их в некотором смысле универсальность. Мол, есть у нас двухточечный кроссовер, и мы будем его "танцевать" всегда и везде, в любую погоду. Использование problem-dependent операторов не является выходом за рамки эволюционного подхода, и за это не четвертуют. Поэтому если получается, что какой-то оператор действительно плохо справляется с задачей, то его можно просто заменить на другой или разработать специализированный оператор. Так, например, поступали при решении задачи комивояжера. Там вообще была эпопея с операторами, и в результате их придумали полдюжины, а то и больше :).

Ответить

Здравствуйте! У меня тоже диплом. Пришлите, пожалуйсто, ваши материалы на .
Заранее благодарна!

Ответить

конкретно к задаче планирования и упаковки.... мучаюсь, ничего не получается ... =(

Ответить