Загрузка...
Учебная работа. Реферат: Генетические алгоритмы 2
Генетические методы в истинное время обширно употребляются для умственной обработки данных и решения задач оптимизации и поиска. Они удачно употребляются для решения ряда экономически важных задач в бизнесе и инженерных разработках. Денежные компании обширно употребляют генетические методы для прогнозирования развития денежных рынков.
Задачки оптимизации – один из самых принципиальных классов задач практического нрава, с которыми мы сталкиваемся раз в день на работе, либо в быту.
Что такое генетические методы, и каким образом генетические методы можно применять для решения задач оптимизации, предлагается узнать в процессе данной курсовой работы.
The Genetic algorithms are broadly used for intellectual data processing and decisions of the problems optimization and of searching for at present times. They are successfully used for decision of the economic significant problems in business and engineering development. The Financial companies broadly use the genetic algorithms for forecasting of the development the financial.
The problems of optimization are one of the most important classes of the problems of the practical character. We have deal with these problems every day at work and at home.
What are the genetic algorithms and how can we use the genetic algorithms for decision of the problems of optimization is offered realize in this scientific work.
СОДЕРЖАНИЕ
ВВЕДЕНИЕ. 4
ГЛАВА 1 ГЕНЕТИЧЕСКИЕ АЛГОРИТМЫ.. 7
1.1 Генетический метод и его индивидуальности. 7
1.2 Главные генетические операторы.. 10
1.3 Работа генетического метода. 12
1.4 Вывод к Главе 1. 16
ГЛАВА 2 задачки ОПТИМИЗАЦИИ.. 17
2.1 Задачки, решаемые при помощи генетических алгоритмов. 17
2.2 Математическая постановка задачки оптимизации. 18
2.3 Пути решения оптимизационных задач. 19
2.4 Вывод к Главе 2. 21
ГЛАВА З РАЗРАБОТКА УЧЕБНОГО ЭЛЕКТРОННОГО ПОСОБИЯ ПО ГЕНЕТИЧЕСКИМ АЛГОРИТМАМ.. 23
3.1 Обоснование выбора программного обеспечения. 23
3.1 Описание программной реализации. 24
ЗАКЛЮЧЕНИЕ. 27
БИБЛИОГРАФИЧЕСКИЙ СПИСОК.. 29
приложение А.. 30
ВВЕДЕНИЕ
Мир, который нас окружает, является весьма сложной системой, которую пробует разгадать человек. Наука разъясняет окружающее и помогает приспособиться к новейшей инфы, получаемой из наружной среды. Почти все из того, что мы лицезреем и смотрим, можно разъяснить теорией эволюции через наследственность, изменение и отбор.
На миропонимание людей очень повлияла теория эволюции Чарльза Дарвина, представленная в работе «Происхождение Видов», в 1859 году. Огромное количество областей научного познания почти всем должно революции, вызванной теорией эволюции и развития. Дарвин нашел основной механизм развития: отбор в соединении с изменчивостью, который разъясняет весьма широкий диапазон явлений, которые мы смотрим в природе. Потому ученые, которые занимались компьютерными исследовательскими работами, также обращались к теории эволюции. Возможность того, что вычислительная система, наделенная ординарными механизмами изменчивости и отбора, могла бы работать по аналогии с законами эволюции в естественных системах, была весьма заманчивой. Она является предпосылкой возникновения ряда вычислительных систем, построенных на принципах естественного отбора.
В природе повсевременно происходит процесс решения задач оптимизации, которые являются одним из самых принципиальных практических классов. Их приходится решать любому из нас на работе и в быту.
Благодаря открытиям, которые делают ученые, современной науке известны все главные механизмы эволюции, связанные с генетическим наследованием. Эти механизмы довольно ординарны по собственной идее, но достаточно эффективны. Обычное моделирование эволюционного процесса на компе дозволяет получить решения почти всех практических задач. Такие модели получили заглавие “генетические методы” и уже обширно используются в разных областях.
В истинное время в мире происходят неизменные конфигурации стратегий и способов решения задач разной направленности. Посреди этих задач есть задачки, решаемые обычным методом, но есть и такие, четкое решение которых отыскать фактически нереально. Конкретно в таковых вариантах используются генетические методы. Они являются действенной процедурой поиска, которая соперничает с иными процедурами. Потому проблематика исследования по теме «Генетические методы» несет животрепещущий
нрав
Объектом
исследования данной курсовой работы являются генетические методы.
Предметом
исследования является применение генетических алгоритмов для нахождения решения задач оптимизации.
Цель курсовой работы
– разработкаучебного электрического пособия, в каком поочередно описываются главные нюансы генетических алгоритмов, также то, каким образом их можно использовать при решении задач оптимизации.
В процессе исследования поставлены последующие задачки
:
1. Сформировать общие представления о генетических методах
и их особенностях;
2. Узнать, какие есть генетические операторы;
3. Выяснить, каким образом происходит работа генетического метода
и его реализация;
4. Выяснить, где могут применяться генетические методы;
5. Узнать какие задачки могут решаться при помощи генетических
алгоритмов;
6. Выявить пути решения задач оптимизации при помощи генетических
алгоритмов;
7. На базе приобретенной инфы сделать электрическое пособие по
основам генетических алгоритмов.
Перед началом работы была выдвинута догадка
– решение задач оптимизации может быть при помощи генетических алгоритмов. Эта догадка будет доказана либо опровергнута в процессе исследования.
Курсовая работа состоит из введения, 3-х глав главный части, заключения, приложения и библиографического перечня.
Во внедрении обусловлена актуальность выбора темы, определены предмет, объект, цель и надлежащие ей задачки исследования, выявлена неувязка и поставлена догадка.
В первой главе рассмотрены общетеоретические вопросцы по теме «Генетические методы». В ней рассматривается, что такое геометрические методы, каковы их индивидуальности, какие есть генетические операторы, как работают геометрические методы.
Во 2-ой главе рассмотрены вопросцы, касающиеся задач оптимизации и внедрения генетических алгоритмов для решения задач такового класса. В ней рассматриваются задачки, которые можно решать при помощи генетических алгоритмов, математическая постановка задач оптимизации и пути их решения.
3-я глава имеет практический нрав. В ней описана программная реализация сотворения электрического пособия по теме «Генетические методы». В приложении описан программный код реализации одной их традиционных оптимизационных задач, решенной при помощи генетического метода – «Задачки коммивояжера». Опосля каждой главы идут обобщающие выводы.
ГЛАВА 1 ГЕНЕТИЧЕСКИЕ АЛГОРИТМЫ
1.1 Генетический метод и его индивидуальности
Генетические методы появились в итоге наблюдения и попыток копирования естественных действий, происходящих в мире {живых} организмов, а именно, эволюции и связанной с ней селекции (естественного отбора) популяций {живых} созданий.
Идею генетических алгоритмов высказал Джон Холланд в 1975 году. Он заинтересовался качествами действий естественной эволюции, в том числе фактом, что эволюционируют хромосомы, а не сами живы существа. Холланд был уверен в способности составить и воплотить в виде компьютерной программки метод, который будет решать сложные задачки так, как это делает природа — методом эволюции. Потому он начал трудиться над методами, оперировавшими последовательностями двоичных цифр (единиц и нулей), получившими заглавие хромосом. Эти методы имитировали эволюционные процессы в поколениях таковых хромосом. Так же, как и в природе, генетические методы производили поиск «не плохих» хромосом без использования какой-нибудь инфы о нраве решаемой задачки. Требовалась лишь некоторая оценка каждой хромосомы, отражающая ее приспособленность. [7]
Генетические методы используются при разработке программного обеспечения, в системах искусственного ума, оптимизации, искусственных нейронных сетях и в остальных отраслях познаний. Необходимо подчеркнуть, что с помощью их решаются задачки, для которых ранее использовались лишь нейронные сети. В этом случае генетические методы выступают просто в роли независящего от нейронных сетей альтернативного способа, созданного для решения той же самой задачки. Генетические методы нередко употребляются вместе с нейронными сетями. Они могут поддерживать
нейронные сети либо напротив, или оба способа ведут взаимодействие в рамках гибридной системы, созданной для решения определенной задачки. Генетические методы также используются вместе с нечеткими системами.
Генетические методы — адаптивные способы поиска, которые в крайнее время нередко употребляются для решения задач многофункциональной оптимизации. Они основаны на генетических действиях био организмов: био популяции развиваются в течение нескольких поколений, подчиняясь законам естественного отбора и по принципу «выживает более адаптированный», открытому Чарльзом Дарвином. Подражая этому процессу генетические методы способны «развивать» решения настоящих задач, если те подходящим образом закодированы.
Главный законнаследования интуитивно понятен любому — он заключается в том, что потомки похожи на родителей. А именно, потомки наиболее адаптированных родителей будут, быстрее всего, одними из более адаптированных особей в собственном поколении. Из биологии мы знаем, что хоть какой организм быть может представлен своим фенотипом, который практически описывает, чем является объект в настоящем мире, и генотипом, который содержит всю информацию о объекте на уровне хромосомного набора. При всем этом любой ген, другими словами элемент инфы генотипа, имеет свое отражение в фенотипе. Таковым образом, для решения задач нам нужно представить любой признак объекта в форме, пригодной для использования в генетическом методе. Все предстоящее функционирование устройств генетического метода делается на уровне генотипа, позволяя обойтись без инфы о внутренней структуре объекта, что и обуславливает его обширное применение в самых различных задачках. [6]
В более нередко встречающейся разновидности генетического метода для представления генотипа объекта используются битовые строчки. При всем этом любому атрибуту объекта в фенотипе соответствует один ген в генотипе объекта. Ген представляет собой битовую строчку, почаще всего фиксированной длины, которая представляет собой
Для кодировки таковых признаков можно применять самый обычной вариант – битовое
Таковым образом, для того, чтоб найти фенотип объекта (другими словами значения признаков, описывающих объект) нам нужно лишь знать значения генов, подходящим сиим признакам, другими словами генотип объекта. При всем этом совокупа генов, описывающих генотип объекта, представляет собой хромосому. В неких реализациях ее также именуют особью. В реализации генетического метода хромосома представляет собой битовую строчку фиксированной длины. При всем этом любому участку строчки соответствует ген. Длина генов снутри хромосомы быть может схожей либо различной. Почаще всего используют гены схожей длины. [9]
Генетические методы работают с совокупой «особей» – популяцией, любая из которых представляет вероятное решение данной трудности. Любая особь оценивается мерой ее «приспособленности» согласно тому, как «отлично» соответственное ей решение задачки. В природе это эквивалентно оценке того, как эффективен организм при конкуренции за ресурсы. Более адаптированные особи получают возможность «воспроизводить» потомство при помощи «перекрестного скрещивания» с иными особями популяции. Это приводит к возникновению новейших особей, которые соединяют внутри себя некие свойства, наследуемые ими от родителей. Менее адаптированные особи с наименьшей вероятностью сумеют воспроизвести потомков, так что те характеристики, которыми они владели, будут равномерно исчезать из популяции в процессе эволюции. время от времени происходят мутации, либо спонтанные конфигурации в генах.[13]
Таковым образом, из поколения в поколение, отличные свойства распространяются по всей популяции. Скрещивание более адаптированных особей приводит к тому, что исследуются более многообещающие участки места поиска. В итоге популяция будет сходиться к хорошему решению задачки. Преимущество генетических алгоритмов заключается в том, что он находит ориентировочные рациональные решения за относительно куцее время.
Генетический метод состоит из последующих компонент:
· Хромосома. Решение рассматриваемой трудности. Состоит из генов.
· Исходная популяция хромосом.
· Набор операторов для генерации новейших решений из предшествующей
популяции.
· Мотивированная функция для оценки приспособленности решений. [11]
1.2 Главные генетические операторы
Обычные операторы для всех типов генетических алгоритмов это:скрещивание, мутация и селекция
Как понятно в теории эволюции важную роль играет то, каким образом признаки родителей передаются потомкам. В генетических методах за передачу признаков родителей потомкам отвечает оператор, который именуется скрещивание
(его также именуют кроссовер либо кроссинговер). Этот оператор описывает передачу признаков родителей потомкам.
Действует он последующим образом:
1. Из популяции выбираются две особи, которые будут родителями;
2. Определяется (обычно случайным образом) точка разрыва;
3. Потомок определяется как конкатенация части первого и второго родителя.
Таковым образом, оператор скрещивание производит обмен частями хромосом меж 2-мя хромосомами в популяции, т. е. делает структуру, основанную на 2-ух структурах – подменой одной части первой структуры на туже область во 2-ой. Потом с вероятностью 0.5 определяется одна из результирующих хромосом в качестве потомка.
Последующий генетический оператор предназначен для того, чтоб поддерживать обилие особей в популяции. Он именуется мутацией
.
При использовании данного оператора любой бит в хромосоме с определенной вероятностью инвертируется.Не считая того, употребляется к тому же так именуемый оператор инверсии, который состоит в том, что хромосома делится на две части, и потом они изменяются местами.
Можно сказать, что инверсия — перестановка в структуре некой ее части напротив, а мутация — стохастическое изменение части хромосом, когда любой ген строчки, которая подвергается мутации, с вероятностью Pmut
(обычно весьма малеханькой) изменяется на иной ген.
Для функционирования генетического метода довольно этих 2-ух генетических операторов, но на практике используют к тому же некие доп операторы либо модификации этих 2-ух операторов. к примеру, кроссовер быть может не одноточечный (с одной точкой разрыва), а многоточечный, когда формируется несколько точек разрыва (почаще всего две). Не считая того, в неких реализациях метода оператор мутации представляет собой инверсию лишь 1-го случаем избранного бита хромосомы.
Оператор селекции
производит отбор хромосом в согласовании со значениями их функции приспособленности.
Более действенные два механизма отбора – элитный отбор и отбор с вытеснением.
Мысль элитного отбора базирована на построении новейшей популяции лишь из наилучших особей репродукционной группы, объединяющей внутри себя родителей, их потомков и мутантов. В главном это разъясняют возможной угрозой досрочной сходимости, отдавая предпочтение пропорциональному отбору. Стремительная сходимость, обеспечиваемая элитным отбором, быть может, когда это нужно, с фуррором возмещена пригодным способом выбора родительских пар, к примеру аутбридингом. Конкретно таковая композиция «аутбридинг — элитный отбор» является одной из более действенных. [3]
2-ой способ – это отбор вытеснением. Будет ли особь из репродукционной группы заноситься в популяцию новейшего поколения, определяется не только лишь величиной ее приспособленности, да и тем, есть ли уже в создаваемой популяции последующего поколения особь с аналогичным хромосомным набором. Из всех особей с схожими генотипами предпочтение поначалу, естественно же, отдается тем, чья приспособленность выше.
Таковым образом, достигаются две цели: во-1-х, не теряются наилучшие отысканные решения, владеющие разными хромосомными наборами, а во-2-х, в популяции повсевременно поддерживается достаточное генетическое обилие. [8]
1.3 Работа генетического метода
Работа генетического метода представляет собой итерационный процесс, который длится до того времени, пока не выполнятся данное число поколений либо какой-нибудь другой аспект останова. На любом поколении генетическим методом реализуется отбор пропорционально приспособленности, кроссовер и мутация.
Схематичное описание функционирования генетического метода (Набросок 1):
Набросок 1 метод работы традиционного генетического метода
Функционирование генетического метода можно обрисовать последующими шагами:
Инициировать исходный момент времени t=0. Случайным образом сформировать исходную популяцию, состоящую из k-особей.
Вычислить приспособленность каждой особи и популяции в целом. задачки.
1. Избрать особь из популяции;
2. С определенной вероятностью (вероятностью кроссовера) избрать вторую особь из популяции и произвести оператор кроссовера;
3. С определенной вероятностью (вероятностью мутации) выполнить оператор мутации;
4. С определенной вероятностью (вероятностью инверсии) выполнить оператор инверсии;
5. Поместить полученную хромосому в новейшую популяцию;
6. Выполнить операции, начиная с пт 3, k-раз;
7. Прирастить номер текущей эры t=t+1;
8. Если выполнилось условие остановки, то окончить работу, по другому переход на шаг 2;
Распишем наиболее тщательно последующие этапы:
1. Выбор родительской пары:
1-ый подход самый обычной – это случайный выбор родительской пары, когда обе особи, которые составят родительскую пару, случайным образом выбираются из всей популяции, при этом неважно какая особь может стать членом нескольких пар. Невзирая на простоту, таковой подход всепригоден для решения разных классов задач. Но он довольно критичен к численности популяции, так как эффективность метода, реализующего таковой подход, понижается с ростом численности популяции.
2-ой метод выбора особей в родительскую пару — так именуемый селективный. Его сущность заключается в том, что «родителями» могут стать лишь те особи, значения приспособленности по популяции, при равной вероятности таковых кандидатов составить супружескую пару. Таковой подход обеспечивает наиболее резвую сходимость метода. Но из-за резвой сходимости селективный выбор родительской пары не подступает тогда, когда ставиться задачка определения
нескольких экстремумов, так как для таковых задач метод, как правило, стремительно сходится к одному из решений.
Остальные два метода формирования родительской пары – инбридинг и аутбридинг. Оба эти способа построены на формировании пары на базе близкого и далекого «родства» соответственно. Под «родством» тут понимается расстояние меж членами популяции как в смысле геометрического расстояния особей в пространстве характеристик. В связи с сиим различают генотипный и фенотипный (либо географический) инбридинг и аутбридинг. Под инбридингом понимается таковой способ, когда 1-ый член пары выбирается случаем, а вторым с большей вероятностью будет очень близкая к нему особь. Аутбридинг же, напротив, сформировывает супружеские пары из очень дальних особей. Внедрение генетических инбридинга и аутбридинга оказалось наиболее действенным по сопоставлению с географическим для всех тестовых функций при разных параметрах метода. Более полезно применение обоих представленных способов для многоэкстремальных задач. Но два этих метода по-разному влияют на области. [10]
2. Механизм отбора:
Обсуждение вопросца о воздействии способа сотворения родительских пар на много генетических алгоритмов и почти всегда они не достаточно похожи на метод, представленный на рис.5. По данной нам причине в истинное время под термином «генетические методы» прячется не одна модель, а довольно широкий класс алгоритмов.[2]
1.4 Вывод к Главе 1
При рассмотрении общих теоретических качеств по теме «Генетические методы», выяснилось, что мысль сотворения алгоритмов, которые могли бы решать различного рода задачки, в том числе и оптимизационные, принадлежит Джону Холланду. В 1975 году им был предложен 1-ый генетический метод. Холланд занимался разработкой алгоритмов, которые могли бы применять механизмы естественного отбора при решении задач.
В общих чертах работу генетического метода можно обрисовать так: он делает популяцию особей, любая из которых является решением задачки, а потом эти особи эволюционируют по принципу «выживает наисильнейший», другими словами остаются только самые рациональные решения. Каждую особь обрисовывает хромосома, хромосома состоит из генов, которые размещаются в определенных позициях хромосомы, т.е. вся наследная информация, либо генотип, хранится в хромосомах.
Работа генетического метода имитирует естественную жизнь, лишь очень облегченную.
Генетические методы создавались как еще один способ решения задач, другой уже имеющимся. Почаще всего генетические методы употребляют для решения оптимизационных задач, в особенности, если классическими методами эти задачки решить весьма тяжело, фактически нереально. В последующей главе будут рассмотрены оптимизационные задачки и то, каким образом их можно решить при помощи генетического метода.
ГЛАВА 2 задачки ОПТИМИЗАЦИИ
2.1 Задачки, решаемые при помощи генетических алгоритмов
Итак, в данной нам главе нами будут рассмотрены задачки оптимизации, их математическая постановка и пути решения.
задачки оптимизации – более всераспространенный и принципиальный для практики класс задач. Их приходится решать хоть какому из нас либо в быту, распределяя свое время меж различными делами, либо на работе, добиваясь наибольшей скорости работы программки либо наибольшей прибыльности компании.
Посреди этих задач есть те, которые решаются обычным методом, но есть и такие, четкое решение которых отыскать фактически нереально.
Генетические методы в различных формах используются к решению почти всех научных и технических заморочек. Генетические методы употребляются при разработке остальных вычислительных структур, к примеру, автоматов либо сетей сортировки. В машинном обучении они употребляются при проектировании нейронных сетей либо управлении роботами. Они также используются при моделировании развития в различных предметных областях, включая био (экология, иммунология и пользующаяся популярностью генетика) и социальные (такие как Экономика и политические системы) системы.
Тем не наименее, пользующееся популярностью применение генетических алгоритмов – оптимизация многопараметрических функций. Большая часть настоящих задач могут быть сформулированы, как поиск рационального значения, где значение – непростая функция, зависящая от определенных входных характеристик. В неких вариантах, необходимо отыскать те значения характеристик, при которых достигается четкое случае, генетические методы – приемлемый способ для поиска «применимых» значений. Сила генетического метода состоит в его возможности манипулировать сразу почти всеми параметрами, которая употребляется в сотках прикладных программ, включая проектирование самолетов, настраивании характеристик алгоритмов и поиске стойких состояний систем нелинейных дифференциальных уравнений.
Генетические методы являются действенной процедурой поиска, которая соперничает с иными процедурами. Эффективность генетических алгоритмов очень зависит от таковых деталей, как способ кодировки решений, операторов, настраивания характеристик, отдельных критериев фуррора.
[1]
2.2 Математическая постановка задачки оптимизации
Постановка задачки оптимизации содержит в себе огромное количество допустимых решений 
и числовую функцию, определенную на этом огромном количестве, которая именуется мотивированной функцией.
недозволено отождествлять аспект (аспекты) оптимальности и мотивированную функцию.
Мотивированная функция – это аналитическая зависимость меж аспектом (аспектами) оптимальности и подлежащими оптимизации параметрами с указанием направления экстремума.
Отличие понятий «аспект» и «мотивированная функция» состоит в последующем:
1. Мотивированная функция может включать в себя наиболее 1-го аспекта.
2. Для мотивированной функции постоянно и непременно указывается вид
экстремума:
Различают два вида задач оптимизации:
1. Задачку минимизации.
2. Задачку максимизации.
Чтоб решить задачку минимизации функции 
на огромном количестве, нужно отыскать таковой вектор (также соответственное тут – наименьшим решением), а — оптимумом (минимумом).
Чтоб решить задачку максимизации функции на огромном количестве, нужно отыскать таковой вектор (также соответственное
В общем виде находится конкретно вектор, т.к., к примеру, при решении двухпараметрической задачки, он будет включать в себя два параметра, трехпараметрической – три параметра и т.д. [1]
2.3 Пути решения оптимизационных задач
Генетический метод — новый, но не единственно вероятный метод решения задач оптимизации. С давнешних пор известны два главных пути решения таковых задач — переборный и локально-градиентный. У этих способов свои плюсы и недочеты, и в любом определенном случае следует помыслить, какой из их избрать.
Переборный способ более прост по собственной сущности. Для поиска рационального решения (точки максимума мотивированной функции) требуется поочередно вычислить значения мотивированной функции во всех вероятных точках, запоминая наибольшее из их.
Недочетом этого способа является большая вычислительная стоимость. А именно, в задачке коммивояжера будет нужно просчитать длины наиболее 1030 вариантов путей, что совсем нереально. Но, если перебор всех вариантов за разумное время вероятен, то можно быть полностью уверенным в том, что отысканное решение вправду нормально.
2-ой пользующийся популярностью метод основан на способе градиентного спуска. При всем этом сначала выбираются некие случайные значения характеристик, а потом эти значения равномерно изменяют, добиваясь большей скорости роста мотивированной функции. Достигнув локального максимума, таковой метод останавливается, потому для поиска глобального оптимума потребуются доп усилия.
Градиентные способы работают весьма стремительно, но не гарантируют оптимальности отысканного решения. Они безупречны для внедрения в так именуемых унимодальных задачках, где мотивированная функция имеет единственный локальный максимум (он же — глобальный).
Обычная практическая задачка, обычно, мультимодальна и многомерна, другими словами содержит много характеристик. Для таковых задач не существует ни 1-го всепригодного способа, который дозволял бы довольно стремительно отыскать полностью четкое решение. [1]
Генетический метод представляет собой комбинацию переборного и градиентного способов. Механизмы кроссинговера (скрещивания) и мутации реализуют переборную часть, а отбор наилучших решений – градиентный спуск.
Другими словами, если на неком огромном количестве задана непростая функция от нескольких переменных, тогда генетический метод является программкой, которая за допустимое время находит точку, где значение функции находится достаточно близко к очень вероятному значению. Выбирая применимое время расчета, получаем наилучшие решения, которые можно получить за это время. [5]
2.4
Вывод к Главе 2
Существует огромное количество вариантов задач оптимизации. В особенности тяжело переоценить их значимость в математической экономике. Во 2-ой главе были рассмотрены задачки, которые можно решать при помощи генетических алгоритмов.
Существует вопросец о том, как целенаправлено применение генетических алгоритмов для решения разных задач. С одной стороны, в арифметике существует довольно большенный класс полностью надежных (в смысле гарантии получения четкого решения) способов решения разных задач. С иной стороны, идет речь о вправду сложных практических задачках, в каких эти надежные способы нередко неприменимы. Часто эти задачки смотрятся так неоглядными, что не предпринимается даже попыток их осмысленного решения.
к примеру, компания, занимающаяся транспортными перевозками, в современных критериях русского бизнеса быстрее предпочтет нанять излишних водителей и повысить цены на свои услуги, чем улучшить маршруты и расписания поездок. На западном рынке, где уже издавна действуют законы наиболее либо наименее добросовестной конкуренции, оптимальность деятель компании существенно влияет на ее доходы и даже может стать решающим фактором для ее выживания. Потому любые идеи, дозволяющие компании стать “умнее” собственных соперников, находят там обширное применение.
Генетические методы — реализация одной из более фаворитных мыслях такового рода. Таковым образом, задав условия жизни в неком виртуальном мире и заселив его представителями с определенными качествами, опосля действий скрещивания, мутации и естественного отбора, аналоги которых происходят и в настоящем мире, мы размеренно получаем особь, характеристики которой отвечают ранее данным требованиям. Данный факт гласит о том, что осознание испытанных веками законов природы дозволяет применять их при решении, чудилось бы, и дальних от нее задач, личным случаем которых являются задачки оптимизации.
Задачки оптимизации – более всераспространенный и принципиальный для практики класс задач. Их приходится решать хоть какому из нас либо в быту, распределяя свое время меж различными делами, либо на работе. Была рассмотрена математическая постановка задач оптимизации, также пути их решения. Для решения задач оптимизации употребляются не только лишь такие способы, как обычной перебор и градиентный спуск, которые не постоянно эффективны, в особенности, если мы имеем дело с тяжелыми в практическом смысле задачками.
Генетические методы довольно действенный метод решения непростых оптимизационных задач, так как соединяет внутри себя комбинацию переборного и градиентного способов. Механизмы кроссинговера (скрещивания) и мутации реализуют переборную часть, а отбор наилучших решений – градиентный спуск.
Выбирая применимое время расчета, получаем наилучшие решения, которые можно получить за это время.
ГЛАВА З РАЗРАБОТКА УЧЕБНОГО ЭЛЕКТРОННОГО ПОСОБИЯ ПО ГЕНЕТИЧЕСКИМ АЛГОРИТМАМ
3.1 Обоснование выбора программного обеспечения
В крайнее время резко возрос энтузиазм к программированию. Это связано с развитием и внедрением в ежедневную жизнь информационно-коммуникационных технологий. Если человек имеет дело с компом, то рано либо поздно у него возникает желание, а время от времени и необходимость, программировать.
Интерактивность – сейчас весьма принципиальное условие для создаваемых приложений, программ, электрических пособий и т. д. Более полный эталон, который гарантирует данное условие, ActionScript для FlashСравнимо не так давно он перевоплотился из обычного языка подготовки сценариев в всеполноценную объектно-ориентированную среду программирования.
Нашей целью является создание электрического пособия, которое позволило бы довольно понятно и просто донести до юзера главные понятия и принципы организации генетического метода и решения с его помощью оптимизационных задач, а именно, задачки коммивояжера, которая является традиционной оптимизационной задачей. ActionScript предоставляет красивую возможность организовать яркий, доступный интерфейс и навигацию. И очередной бесспорный плюс при разработке учебника на ActionScript: внедрение готового продукта, как самостоятельную программку (публикация готового продукта с .exe расширением).
Потому для сотворения электрического пособия по основам генетических алгоритмов был избран Flash
Для того, чтоб показать, как реализуется генетический метод при решении задачки коммивояжера, была выбрана среда программирования BorlandDelphi 6.0.
3.1 Описание программной реализации
Перед началом разработки электрического пособия был подготовлен материал, который будет представлен в нем. Основным аспектом при отборе материала стала его полезность и возможность поведать о генетических методах и задачках оптимизации в общих чертах на доступном языке.
Потом были определены структура и дизайн пособия.
Электрическое учебное пособие создавалась при помощи MacromediaFlashMX2004.
Размещение материала было сформировано наподобие обыкновенной книжки с заглавием, содержанием и возможностью перелистывания страничек.
На первой страничке было расположено заглавие пособия и его содержание. Содержание состоит из 3-х пт, которые в свою очередь делятся на подпункты, дозволяющие осветить рассматриваемую тему с нескольких сторон (Набросок 2):
Набросок 2 Содержание электрического пособия
Перелистывание меж слайдам осуществляется за счет навигации в виде 2-ух стрелок «вперед»-«вспять», расположенных в правом нижнем углу. Не считая того, постоянно существует возможность возвратиться к страничке содержания с хоть какой странички пособия. Для этого довольно пользоваться клавишей «Main». Для того, чтоб клавиши навигации работали, на их был написан сценарий на ActionScript.
Подпункты на страничке содержания выполнены в виде ссылок. Довольно надавить на интересующий вопросец и раскроется его страница.
Любой пункт и подпункт презентации размещен на отдельной страничке. Для презентации был избран нейтральный голубой фон. Вся цветовая палитра выдержана. шрифты были подобраны таковым образом, чтоб можно было прочесть без затруднений. В презентации находятся картинки и таблицы, наиболее наглядно объясняющие те либо другие нюансы вопросца (Набросок 3):
Набросок 3 Пример странички с приятными пояснениями
И, в конце концов, на крайнем шаге мы публикуем наше пособие в .exe формате, для того, чтобы наша разработка запускалась на компе хоть какого юзера, в не зависимости от того, установлен на его компе Flashлибо нет.
В электрическом пособии в качестве примера оптимизационной задачки, которую можно решить при помощи генетического метода, представлена задачка коммивояжера. Для иллюстрации реализации генетического метода при решении задачки была сотворена программка в BorlandDelphi 6.0, которая, а именно указывает решение задачки, представленной в электрическом пособии (Набросок 4):
Набросок 4 Реализация задачки коммивояжера при помощи генетического метода
Программный код решения задачки коммивояжера описан в Приложении А.
ЗАКЛЮЧЕНИЕ
При исследовании вопросца о применении генетических алгоритмов для решения задач оптимизации, мы разглядели достаточное количество качеств данной нам темы. Во-1-х, узнали общую теоретическую информацию, узнали кто, когда и для чего вымыслил генетические методы, что они из себя представляют, и какую имеют аналогию с естественным отбором в природе. Также мы узнали принцип работы генетических алгоритмов и то, с помощью каких главных операторов она осуществляется.
Также было выяснено, какие задачки можно решать при помощи генетических алгоритмов. Посреди таковых задач находятся и особенный класс – оптимизационные.
Были рассмотрены пути решения оптимизационных задач. Не считая генетических алгоритмов употребляются также способ перебора и градиентный спуск. Генетические методы неплохи тем, что соединяют внутри себя два сиим обычных способа.
Итак, наша догадка о том, что задачки оптимизации можно решить при помощи генетических алгоритмов отыскала свое доказательство.
В заключении, можно привести случаи, когда применение генетических алгоритмов не только лишь может быть, да и является наилучшим выбором.
1-ый вариант, когда не известен метод четкого решения задачки. Если мы знаем, как оценить приспособленность хромосом, то постоянно можем вынудить генетический метод решать эту задачку.
2-ой вариант: когда метод для четкого решения существует, но он весьма сложен в реализации, просит огромных издержек времени и средств.
Что все-таки касается недочетов, то в общем случае генетические методы не находят рационального решения весьма тяжелых задач. Если среднее решение задачки (к примеру, задачка коммивояжера с весьма огромным числом городов) не быть может найдено классическими методами, то и генетический метод навряд ли отыщет оптимум.
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
1. Вентцель Е.С. «Исследование операций», — М.: 1972 г.
2. «Генетические методы: почему они работают?»/, «Компьютерра», № 11, 1999
3. «Генетические методы и машинное обучение »
HTTP://www.math.tsu.ru/russian/
center/ai_group/ai_collection/docs/faqs/ai/part5/faq3.html
4. Исаев С. Популярно о генетических методах
www.algolist.Manual.ru
5. «Нейропроект. Аналитические технологии XXI века» http://www.neuroproject.ru/genealg.php#what
6. Коршунов Ю.М. «Математические базы кибернетики. Для студентов вузов», — М.: 1987 г., стр. 67-89
7. «Лекции по нейронным сетям и генетическим методам»
HTTP://infoart.baku.az/inews/300
00007.htm
8. Струнков Т. «Что такое генетические методы?» www.neuroproject.ru/papers.htm
9. Рутковская Д., Пилиньский М., Рутковский Л. «Нейронные сети, генетические методы и нечеткие системы»: Пер. с польск. И. Д. Рудинского. — М.: Жгучая линия -Телеком, 2006. — 452 с: ил.
10. «Факультет вычислительной арифметики и кибернетики МГУ (ВМиК)»
HTTP://cmc.cs.msu.su/labs/lvk/materials/tez_sapr99
_1.html
11. «(EHIPS) Генетические методы»
HTTP://www.iki.rssi.ru/ehips/gene
tic.htm
12. «Neural Bench Development»
HTTP://www.neuralbench.ru/rus/theory/genetic.htm
13. «SENN Генетические Методы»
HTTP://fdmhi
.mega.ru/ru/senn_ga.htm
ПРИЛОЖЕНИЕ А
Программный код решения задачки коммивояжера при помощи генетических алгоритмов в BorlandDelphi 6.0
Const
x=5;
var
Form1: TForm1;
town: array [1..21,1..25] of string; //
implementation
{$R *.dfm}
procedure TForm1.N3Click(Sender: TObject); //
const
mbYesNo = [mbYes, mbNo];
begin
if MessageDlg(‘Выдействительнохотитевыйти?’, mtConfirmation, mbYesNo, 0) = mrYes
then close;
end;
procedure TForm1.N2Click(Sender: TObject); //
begin
ShowMessage(‘Демонстрация задачки коммивояжёра, решенной при помощи генетических алгоритмов. Дляучебногопособия «Генетическиеалгоритмы»!!!’);
end;
procedure TForm1.Button1Click(Sender: TObject);
var i, j, k, a, b, s1, s2, p: integer;
begin
for i:=1 to x do
begin
StringGrid1.Cells[i,i]:=’0′; //
for j:=1 to x do
StringGrid1.Cells[i,j]:=StringGrid1.Cells[j,i]; //
еnd;
town[1,1]:=’12345′; //
a:=2; //
for k:=1 to 4 do
begin //
town[1,a]:=town[1,a-1]; //
town[1,a][4]:=town[1,a-1][5]; //
town[1,a][5]:=town[1,a-1][4];
town[1,a+1]:=town[1,a-1]; //
town[1,a+1][3]:=town[1,a-1][5]; //
town[1,a+1][5]:=town[1,a-1][3];
town[1,a+2]:=town[1,a+1]; //
town[1,a+2][5]:=town[1,a+1][4]; //
town[1,a+2][4]:=town[1,a+1][5];
town[1,a+3]:=town[1,a+2]; //
town[1,a+3][3]:=town[1,a+2][5]; //
town[1,a+3][5]:=town[1,a+2][3];
town[1,a+4]:=town[1,a+3]; //
town[1,a+4][5]:=town[1,a+3][4]; //
town[1,a+4][4]:=town[1,a+3][5];
town[1,a+5]:=town[1,a+4]; //
town[1,a+5][5]:=town[1,a+4][2]; //
town[1,a+5][2]:=town[1,a+4][5];
a:=a+6; //
end;
a:=0; //
s2:=9999999;
for i:=1 to 24 do
begin
s1:=0;
for p:=1 to x do
begin
a:=StrToInt(town[1,i][p]);
if p=5 then b:=StrToInt(town[1,i][p-4])
else b:=StrToInt(town[1,i][p+1]);
s1:=s1+StrToInt(StringGrid1.Cells[b,a]);
end;
if s1<s2 then
begin
s2:=s1;
town[2,1]:=town[1,i];
end;
end;
for i:=1 to 25 do
StringGrid2.Cells[1,i]:=town[1,i];
StringGrid2.Cells[2,1]:=IntToStr(s2);
Edit2.Text:=town[2,1]; //
Edit1.Text:=IntToStr(s2); //
end;
procedure TForm1.Button3Click(Sender: TObject); //
var i,j: integer;
begin
StringGrid1.ColCount:=x+1;
StringGrid1.RowCount:=x+1;
StringGrid2.ColCount:=x+1;
StringGrid2.RowCount:=26;
fori:=1 toxdo//
for j:=1 to x do
StringGrid1.Cells[i,j]:=» »; //
fori:=1 toxdo
begin
StringGrid1.Cells[i,i]:=’0′;
StringGrid1.Cells[i,0]:=IntToStr(i);
StringGrid1.Cells[0,i]:=IntToStr(i);
StringGrid2.Cells[i,0]:=IntToStr(i);
end;
fori:=1 tox*2 do //
StringGrid2.Cells[0,i]:=IntToStr(i);
end;
end.
]]>