Автор работы: Пользователь скрыл имя, 04 Февраля 2013 в 16:23, курсовая работа
В нашей жизни мы регулярно сталкиваемся с необходимостью решения
оптимизационных и прогностических задач. Так, например, доход любой
компании определяется качеством этих решений - точностью прогнозов и
оптимальностью выбранных стратегий.
Введение:
1. Теория алгоритмов. Задача коммивояжера.
2. Генетические алгоритмы. Общее описание. Математический аппарат
3. Непрерывные генетические алгоритмы. Математический аппарат.
4. Заключение.
5. Список использованной литературы.
SBX (англ.: Simulated Binary Crossover) - кроссовер, имитирующий двоичный.
Был разработан
в 1995 году исследовательской
Deb'а.
Как следует из его названия,
этот кроссовер моделирует
работы
двоичного оператора скрещивани
SBX кроссовер
был получен следующим
обнаружено важное свойство - среднее значение функции приспособленности
оставалось неизменным у родителей и их потомков, полученных путем
скрещивания. Затем автором было введено понятие силы поиска кроссовера
(search power). Это количественная величина, характеризующая распределение
вероятностей появления любого потомка от двух произвольных родителей.
Первоначально была рассчитана сила поиска для одноточечного двоичного
кроссовера,
а затем был разработан
силой
поиска. В нем сила поиска
вероятностей случайной величины 0x01 graphic
:
Для генерации
потомков используется
выражение для 0x01 graphic
. Создаются два потомка 0x01 graphic
, 0x01 graphic
, где 0x01 graphic
, 0x01 graphic
- число, полученное по формуле:
0x01 graphic
В формуле 0x01 graphic
- случайное
число, распределенное по
- параметр кроссовера.
На рисунке
приведена геометрическая
при скрещивании двух хромосом, соответствующих вещественным числам 2 и 5.
Видно, как параметр n влияет на конечный результат: увеличение n влечет за
собой
увеличение вероятности
наоборот.
Эксперименты автора SBX кроссовера показали, что он во многих случаях
эффективнее BLX, хотя, очевидно, что не существует ни одного кроссовера,
эффективного во всех случаях. Исследования показывают, что использование
нескольких различных операторов кроссовера позволяет уменьшить вероятность
преждевременной сходимости, т.е. улучшить эффективность алгоритма
оптимизации
в целом. Для этого могут
использоваться специальные
изменяющие
вероятность применения
зависимости от его «успешности», или использование гибридных кроссоверов,
которых
в настоящее время
случае, если перед Вами стоит задача оптимизации в непрерывных
пространствах, и Вы планируете применить эволюционные техники, то следует
сделать выбор в пользу непрерывного генетического алгоритма.
4. Заключение
За последние
годы объёмы экономической
раз, и это является дополнительным стимулом для многих учёных, работающих
в области анализа данных, теории информации и теории алгоритмов,
заниматься генетическими алгоритмами.
Очевидно,
этим объясняется появление
языке
(на других языках уже опублико
отметить, что пока многие публикации частично (в большей или меньшей
степени)
повторяют друг друга и может
создаться ложное
том,
что теория генетических
как непрерывные генетические алгоритмы, - тема узкая и исчерпываемая
двадцатью страницами данной работы. На самом же деле есть не только
теория, но и практика генетических алгоритмов. В настоящее время известно
о существовании более пятисот программных продуктов, в том или ином виде
использующих
генетические алгоритмы для
прогностических задача.
Также
стоит отметить, что талантливые
программисты создали
игру, базирующуюся
на наработках теории генетичес
называется «Амёбы: Борьба видов» (http://amebas.ru). Суть игры заключается
в том, что каждый игрок «выращивает» на своём компьютере колонию амёб.
Каждая амёба имеет свой генотип и ведёт борьбу за выживание. В каждом
поколении в ходе сражений часть из них остаётся в проигрыше и не получает
возможности размножаться. По ходу развития (с каждым следующим поколением)
амёбы
накапливают в себе всё больше
и больше генетической
в некоторое время проводятся Интернет-турниры, на которые каждый игрок
выставляет свою лучшую амёбу. В игре учитываются разные возможности
скрещивания, возможность направить отбор в том или ином направлении,
регулировка количества и силы мутаций и прочие настройки.
В заключение
можно сказать, что мои
алгоритмов являются очень оптимистичными по двум причинам:
1. С
повышением вычислительной
перехода на квантовые или молекулярные компьютеры) станет возможным
моделировать при помощи генетических алгоритмов всё более и более
сложные ситуации.
2. Не исключено, что учёные, работающие в области классической теории
алгоритмов, найдут решение одной
из NP-полных задач, и тогда
решаемыми все алгоритмы, относ
5. Список использованной литературы.
1. «АНАЛИТИЧЕСКИЕ ТЕХНОЛОГИИ для прогнозирования и анализа данных», 2008.
«НейроПроект»
2. http://www.gotai.ru
3. http://basegroup.ru
4. http://ru.wikipedia.org
Гамильтоновым циклом в графе называют простой цикл, содержащий все вершины
графа ровно по одному разу. По материалам Википедии - свободной
энциклопедии.
NP-полные задачи — это класс задач, лежащих в классе NP, то есть для
которых пока не найдено быстрых алгоритмов решения, но проверка того,
является ли данное решение правильным, проходит быстро. По материалам
Википедии - свободной энциклопедии.
Информация о работе Генетические алгоритмы и их практическое применение