Генетические алгоритмы в изобретательских задачах

Рассмотрим теперь понятие рекомбинации. Функция рекомбинации определяет, как новая, генерация хромосом будет построена из родителей и потомков. Другими словами, функция

Генетические алгоритмы в изобретательских задачах

Курсовой проект

Менеджмент

Другие курсовые по предмету

Менеджмент

Сдать работу со 100% гаранией

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Генетические алгоритмы в изобретательских задачах

 

Введение

 

Изобретательство - древнейшее занятие человека. С изобретением первых орудий труда и начинается история человека. Затем изобретались новые вещи и технологии их изготовления, отношения между людьми и способы их выяснения, приёмы ведения хозяйства и управления оным, способы делать деньги и считать их.… За тысячи лет, прошедшие с тех пор, все изменилось, неизменным остался только метод создания новых изобретений - метод проб и ошибок (МПиО).

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

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

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

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

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

ГА - это не просто случайный поиск. Они эффективно используют информацию, накопленную в процессе эволюции. Цель ГА состоит в том, чтобы:

.абстрактно и формально объяснить адаптацию процессов в ЕС и интеллектуальной ИС;

.смоделировать естественные эволюционные процессы для эффективного решения оптимизационных задач науки и техники.

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

ГА, согласно, отличаются от других оптимизационных и поисковых процедур следующим:

.работают в основном не с параметрами задачи, а с закодированным множеством параметров;

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

.используют целевую функцию, а не ее различные приращения для оценки качества принятия решений;

.применяют не детерминированные, а вероятностные правила анализа оптимизационных задач.

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

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

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

1. Понятия и определения теории генетических алгоритмов

генетический алгоритм изобретательская задача

Приведем некоторые понятия и определения из теории ГА. Все ГА работают на основе начальной информации, в качестве которой выступает популяция альтернативных решений Р. Популяция Р= {р1, р2, …,рi,…,рNp}есть множество элементов рi. Здесь Np- размер популяции. Каждый элемент этой популяции Рi,как правило, представляет собой одну или несколько хромосом, или особей, или индивидуальностей (альтернативных упорядоченных или неупорядоченных решений). Хромосомы состоят из генов (элементы, части закодированного решения), и позиции генов в хромосоме называются лоци или локус для одной позиции, т. е. ген - под-элемент (элемент в хромосоме), локус - позиция в хромосоме, аллель - значение гена.

Гены могут иметь числовые или функциональные значения. Обычно эти числовые значения берутся из некоторого алфавита. Генетический материал элементов обычно кодируется на основе двоичного алфавита {0,1},хотя можно использовать буквенные, а также десятичные и другие алфавиты. Примером закодированной хромосомы длины семь на основе двоичного алфавита может служить хромосома рi = (0001101).Элементы в ГА часто называют родителями. Родители выбираются из популяции на основе заданных правил, а затем смешиваются (скрещиваются) для производства «детей» (потомков). Дети и родители создают новую популяцию. Генерация, т. е. процесс реализации одной итерации алгоритма, называется поколением.

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

Каждый элемент в популяции имеет определенный уровень качества, который характеризуется значением ЦФ (в литературе иногда называется функция полезности или пригодности - fitness). ЦФ используется в ГА для сравнения решений между собой и выбора из них лучших. Основная задача генетических алгоритмов состоит в оптимизации целевой функции. Другими словами, ГА анализирует популяцию хромосом, представляющих комбинацию элементов из некоторого множества, и оптимизирует ЦФ, оценивая каждую хромосому. Генетические алгоритмы манипулируют популяцией хромосом на основе механизма натуральной эволюции.

Каждая популяция обладает наследственной изменчивостью. Это означает, что имеет место случайное отклонение от наиболее вероятного среднего значения ЦФ. Отклонение описывается нормальным законом распределения случайных величин, но, в отличие от ЕС, наследственная изменчивость не затухает, как всякая флуктуация. При этом наследственные признаки закрепляются, если они имеют приспособительный характер, т. е. обеспечивают популяции лучшие условия существования и размножения.

Так же как процесс эволюции начинается с начальной популяции, так и алгоритм начинает свою работу с создания начального множества конкурирующих между собой решений оптимизационной задачи. Затем эти «родительские» решения создают «потомков» путем случайных и направленных изменений. После этого оценивается эффективность решений, и они подвергаются селекции. Как и в ЕС, здесь действует принцип «выживания сильнейших», наименее приспособленные решения «погибают», а затем процесс повторяется вновь.

ГА в зависимости от размера популяции разделяют на:

.стационарного состояния;

.поколенческие.

В стационарных ГА размер популяции является входным постоянным параметром, задаваемым ЛПР. В поколенческих ГА разрешается увеличивать или уменьшать размер популяции в каждой последующей генерации. Следует отметить, что речь в основном идет о появлении Np + N1 потомков (N1>> 1), прежде чем начинает реализовываться оператор отбора, устраняющий N1хромосом с меньшей ЦФ. Вопросы удаления «лишних» хромосом, как в стационарных, так и в поколенческих ГА, основаны на нескольких эвристиках:

.случайное равновероятное удаление хромосом;

.удаление N1 хромосом, имеющих худшее значение ЦФ;

.удаление хромосом на основе обратно пропорционального значения ЦФ;

.удаление хромосом на основе заданной турнирной стратегии.

Можно предложить еще ряд эвристик удаления, но удаление худших хромосом может привести к преждевременной утрате разнообразия и, следовательно, к попаданию ЦФ в локальный оптимум. Оставление в популяции большого числа хромосом с «плохой» ЦФ приведет к слепому поиску.

Выделяют три особенности алгорит

Похожие работы

1 2 3 4 5 > >>