Генетические алгоритмы (простой пример). Разработка программы

Размещено на http://www.allbest.ru/

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РЕСПУБЛИКИ БЕЛАРУСЬ

БЕЛОРУССКИЙ НАЦИОНАЛЬНЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Факультет информационных технологий и робототехники (ФИТР)

Кафедра программного обеспечения вычислительной техники и автоматизированных систем

КУРСОВАЯ РАБОТА

по дисциплине: "Основы алгоритмизации и программирования"

на тему: "Генетические алгоритмы (простой пример). Разработка программы"

Выполнил: ст. гр. 10701114 Барковский А.С.

Приняла: ст. преподаватель Борисова И.М.

Минск - 2015

Содержание

• Введение
• 1. Теоретический вопрос
• 1.1 Естественный отбор в природе
• 1.2 Представление объектов. Кодирование признаков
• 1.3 Основные генетические операторы
• 1.4 Схема функционирования генетического алгоритма
• 1.5 Задачи, решаемые с помощью генетических алгоритмов
• 1.6 Математическая постановка задачи оптимизации
• 2. Практический раздел
• 2.1 Постановка задачи
• 2.2 Описание программы
• 2.3 Контрольные примеры
• 2.4 Схемы алгоритмов
• Заключение
• Список использованной литературы
• Приложение 1 (программа со стеком на основе массива)
• Приложение 2 (программа со стеком на основе списка)


Введение

Природа поражает своей сложностью и богатством проявлений. Среди примеров можно назвать сложные социальные системы, иммунные и нейронные системы, сложные взаимосвязи между видами. Они - всего лишь некоторые из чудес, ставшие очевидными при глубоком исследовании природы вокруг нас. Наука - это одна из систем, которая объясняет окружающее и помогает приспособиться к новой информации, получаемой из внешней среды. Многое из того, что мы видим и наблюдаем, можно объяснить теорией эволюции через наследственность, изменение и отбор.

На мировоззрение людей сильно повлияла теория эволюции Чарльза Дарвина, представленная в работе "Происхождение Видов", в 1859 году. Множество областей научного знания многим обязана революции, вызванной теорией эволюции и развития. Но Дарвин, подобно многим современникам, предполагающим, что в основе развития лежит естественный отбор, не мог не ошибаться. Например, он не смог показать механизм наследования, при котором поддерживается изменчивость. Однако Дарвин обнаружил главный механизм развития: отбор в соединении с изменчивостью. Во многих случаях, специфические особенности развития через изменчивость и отбор все еще не бесспорные, однако, основные механизмы объясняют невероятно широкий спектр явлений, наблюдаемые в Природе. Поэтому не удивительно, что ученые, занимающиеся компьютерными исследованиями, в поисках вдохновения обратились к теории эволюции. Возможность того, что вычислительная система, наделенная простыми механизмами изменчивости и отбора, могла бы функционировать по аналогии с законами эволюции в естественных системах, была очень привлекательной. Эта надежда является причиной появления ряда вычислительных систем, построенных на принципах естественного отбора. Итак, в природе постоянно происходит процесс решения задач оптимизации. Задачи оптимизации - наиболее распространенный и важный для практики класс задач. Их приходится решать каждому из нас либо в быту, распределяя свое время между различными делами, либо на работе, добиваясь максимальной скорости работы программы или максимальной доходности компании - в зависимости от должности. Благодаря открытиям последних ста лет современной науке известны все основные механизмы эволюции, связанные с генетическим наследованием. Эти механизмы достаточно просты по своей идее, но остроумны (если к природе применимо это слово) и эффективны. Удивительно, но простое моделирование эволюционного процесса на компьютере позволяет получить решения многих практических задач. Такие модели получили название "генетические алгоритмы" и уже широко применяются в различных областях.

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

Объектом изучения данной курсовой работы являются генетические алгоритмы.

Предмет изучения - применение генетических алгоритмов для нахождения решения оптимизационной задачи.

Методы исследования:

o сбор и анализ литературных источников по данной теме;

o изучение особенностей создания и использования генетических алгоритмов;

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

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

Задачи:

1. Проанализировать возможности генетических алгоритмов;

2. Изучить особенности генетических алгоритмов;

3. Создание электронного пособия по основам генетических алгоритмов.



1. Теоретический вопрос

1.1 Естественный отбор в природе

"XIX веке Чарльз Дарвин совершил кругосветное плавание, собирая информацию для теории эволюции на основе естественного отбора, при котором выживает сильнейший. Мог ли он предполагать, что сто лет спустя математики будут использовать эту теорию для решения задачи об оптимальном маршруте кругосветного путешествия с остановками на многих маленьких островах?.." (Автор: РОСС КЛЕМЕНТ. Опубликовано в журнале "Компьютера" №11 от 16 марта 1999 года).

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

Основной закон наследования интуитивно понятен каждому - он состоит в том, что потомки похожи на родителей. В частности, потомки более приспособленных родителей будут, скорее всего, одними из наиболее приспособленных в своем поколении. Чтобы понять, на чем основано это сходство, нужно немного углубиться в построение естественной клетки - в мир генов и хромосом [4].

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

При наследовании возможны мутации из-за радиоактивности или других влияний, в результате которых могут измениться некоторые гены в половых клетках одного из родителей. Измененные гены передаются потомку и придают ему новые свойства. Если эти новые свойства полезны, они, скорее всего, сохранятся в данном виде - при этом произойдет скачкообразное повышение приспособленности вида. Впервые подобный алгоритм был предложен в 1975 году Джоном Холландом (John Holland) в Мичиганском университете. Он получил название "репродуктивный план Холланда" и лег в основу практически всех вариантов генетических алгоритмов [8]. Однако, перед тем как мы его рассмотрим подробнее, необходимо остановится на том, каким образом объекты реального мира могут быть закодированы для использования в генетических алгоритмах.

1.2 Представление объектов. Кодирование признаков

Из биологии мы знаем, что любой организм может быть представлен своим фенотипом, который фактически определяет, чем является объект в реальном мире, и генотипом, который содержит всю информацию об объекте на уровне хромосомного набора. При этом каждый ген, то есть элемент информации генотипа, имеет свое отражение в фенотипе [9]. Таким образом, для решения задач нам необходимо представить каждый признак объекта в форме, подходящей для использования в генетическом алгоритме. Все дальнейшее функционирование механизмов генетического алгоритма производится на уровне генотипа, позволяя обойтись без информации о внутренней структуре объекта, что и обуславливает его широкое применение в самых разных задачах.

В наиболее часто встречающейся разновидности генетического алгоритма для представления генотипа объекта применяются битовые строки. При этом каждому атрибуту объекта в фенотипе соответствует один ген в генотипе объекта. Ген представляет собой битовую строку, чаще всего фиксированной длины, которая представляет собой значение этого признака.

Для кодирования таких признаков можно использовать самый простой вариант - битовое значение этого признака. Тогда нам будет весьма просто использовать ген определенной длины, достаточной для представления всех возможных значений такого признака. Таким кодом является код Грея, который целесообразно использовать в реализации генетического алгоритма [9]. Значения кодов Грея рассмотрены в таблице ниже:

Двоичное кодирование	Кодирование по коду Грея
десятичное	двоичное	шестнадцатеричное	десятичное	двоичное	шестнадцатеричное
0	000	0h	0	0000	0h
1	0001	1h	1	0001	1h
2	0010	2h	3	0011	3h
3	0011	3h	2	0010	2h
4	0100	4h	6	0110	6h
5	0101	5h	7	0111	7h
6	0110	6h	5	0101	5h
7	0111	7h	4	0100	4h
8	1000	8h	12	1100	Ch
9	1001	9h	13	1101	Dh
10	1010	Ah	15	1111	Fh
11	1011	Bh	14	1110	Eh
12	1100	Ch	10	1010	Ah
13	1101	Dh	11	1011	Bh
14	1110	Eh	9	1001	9h
15	1111	Fh	8	1000	8h

Таким образом, для того, чтобы определить фенотип объекта (то есть значения признаков, описывающих объект) нам необходимо только знать значения генов, соответствующим этим признакам, то есть генотип объекта. При этом совокупность генов, описывающих генотип объекта, представляет собой хромосому. В некоторых реализациях ее также называют особью. Таким образом, в реализации генетического алгоритма хромосома представляет собой битовую строку фиксированной длины. При этом каждому участку строки соответствует ген. Длина генов внутри хромосомы может быть одинаковой или различной. Чаще всего применяют гены одинаковой длины [10]. Рассмотрим пример хромосомы и интерпретации ее значения. Допустим, что у объекта имеется 5 признаков, каждый закодирован геном длинной в 4 элемента. Тогда длина хромосомы будет 5*4=20 бит.

1.3 Основные генетические операторы

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

o из популяции выбираются две особи, которые будут родителями;

o определяется (обычно случайным образом) точка разрыва;

o потомок определяется как конкатенация части первого и второго родителя.

Рассмотрим функционирование этого оператора.

Хромосома_1:	0000000000
Хромосома_2:	1111111111

Допустим, разрыв происходит после 3-го бита хромосомы, тогда получаем.

Хромосома_1:	0000000000	"	000	1111111	Результирующая хромосома 1
Хромосома_2:	1111111111	"	111	0000000	Результирующая

Итак, рассмотрим все же операторы по порядку:

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

Пример: из (A, B, C, D, E) и (a, b, c, d, e) получится (A, B, c, d, E).

Затем с вероятностью 0,5 определяется одна из результирующих хромосом в качестве потомка.

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

000	1111111	"	1111111	000

2) инверсия - перестановка в структуре некоторой ее части наоборот

Пример: из (1, 1, 0, 1, 0, 0, 1, 0) получится (1, 1, 0, 0, 1, 0, 1, 0).

3) мутация - замена в структуре одного из значений случайно выбранной компоненты

Пример: из (1, 1, 0, 1, 0, 0, 1, 0) получится (1, 1, 0, 1, 1, 0, 1, 0).

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

1.4 Схема функционирования генетического алгоритма

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

Инициировать начальный момент времени t=0. Случайным образом сформировать начальную популяцию, состоящую из k особей.

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

1. Выбрать особь из популяции.

2. С определенной вероятностью (вероятностью кроссовера) выбрать вторую особь из популяции и произвести оператор кроссовера.

3. С определенной вероятностью (вероятностью мутации) выполнить оператор мутации.

4. С определенной вероятностью (вероятностью инверсии) выполнить оператор инверсии.

5. Поместить полученную хромосому в новую популяцию.

6. Выполнить операции, начиная с пункта 3, k раз.

7. Увеличить номер текущей эпохи t=t+1.

8. Если выполнилось условие остановки, то завершить работу, иначе переход на шаг 2 [13].

Распишем более подробно следующие этапы:

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

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

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

2. Механизм отбора. Обсуждение вопроса о влиянии метода создания родительских пар на поведение генетического алгоритма невозможно вести в отрыве от реализуемого механизма отбора при формировании нового поколения. Наиболее эффективные два механизма отбора элитный и отбор с вытеснением.

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

1.5 Задачи, решаемые с помощью генетических алгоритмов

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

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

1.6 Математическая постановка задачи оптимизации

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

Нельзя отождествлять критерий (критерии) оптимальности и целевую функцию.

Целевая функция - это аналитическая зависимость между критерием (критериями) оптимальности и подлежащими оптимизации параметрами с указанием направления экстремума.

Отличие понятий "критерий" и "целевая функция" состоит в следующем:

1. Целевая функция может включать в себя более одного критерия.

2. Для целевой функции всегда и обязательно указывается вид экстремума:

Различают два вида задач оптимизации:

o Задачу минимизации.

o Задачу максимизации.

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

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

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



2. Практический раздел

2.1 Постановка задачи

Разработать программу, реализующую алгоритм стека (20 элементов). Задача решается в двух вариантах: статическом (на основе массива структур) и динамическом. В качестве элемента стека выбрать структуру, соответствующую индивидуальному варианту.

Магазин:

1. Номер;

2. Название;

3. Фамилия директора;

4. Кол-во сотрудников;

5. Годовой доход.

Предусмотреть заполнение стека из файла (подготовить файл на 20 элементов).

Предусмотреть многоуровневое меню:

1) Заполнение стека

a) с консоли (циклически)

b) из файла (выбор файла, тек. папка, любая папка)

2) Удаление элемента из стека (циклически)

a) безвозвратно

b) с сохранением в файл

3) Очистка стека (с выводом удаляемых элементов)

a) безвозвратно

b) с сохранением в файл

4) Вывод элементов, содержащихся в стеке

a) на экран

b) в файл

5) Вывод количества элементов в стеке

6) Выход

Реализовать алгоритм обработки исключений.

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

2.2 Описание программы

Стек в программе организован с помощью класса-контейнера stack. Имеются две реализации стека: в виде массива и однонаправленного списка. Т.к. реализация скрыта от программы-клиента, можно использовать любой из вариантов класса stack без изменения остальной части программы. Интерфейс составляют объявления функций push (поместить в стек), pop (извлечь из стека), get_amount (получение количества элементов в стеке), output (вывод содержимого стека в поток без извлечения элементов) и конструктора класса, который принимает число элементов в стеке. Функции push и popвозвращают значение типа bool для сообщения о переполнении или отсутствии элементов в стеке.

Стек на основе массива:

class stack

{

private:

EMPLOYEE*elements;

intamount;//количествоэлементоввмассиве

int max;

public:

stack(int size)

{

elements=new EMPLOYEE [size];

max=size;

amount=0;

}

bool push(EMPLOYEE&in)

{

if(amount<max)

{

elements [amount++]=in;

returntrue;

}

returnfalse;

}

bool pop(EMPLOYEE&out)

{

if(amount>0)

{

out=elements [--amount];

returntrue;

}

returnfalse;

}

intget_amount()//получениеколичестваэлементов

{

return amount;

}

voidoutput(ostream&strm)//выводсодержимогостекавпотокбезизвлеченияэлементов

{

for(inti=amount;i>0;i--) elements [i-1].output(strm);

}

~stack()

{

delete []elements;

}

};

Стекнаосновесписка:

class stack

{

private:

struct node//элементсписка

{

EMPLOYEE elem;

node*next;

}*top;//указатель на вершину стека

int amount;//количество элементов в стеке

int max;//максимальное количество элементов в стеке

public:

stack(int size)

{

top=NULL;

max=size;

amount=0;

}

bool push(EMPLOYEE &in)

{

if(amount<max)

{

node*p=top;

top=new node;

top->elem=in;

top->next=p;

amount++;

returntrue;

}

returnfalse;

}

bool pop(EMPLOYEE &out)

{

if(amount>0)

{

out=top->elem;

node*p=top->next;

delete top;

top=p;

amount--;

returntrue;

}

returnfalse;

}

intget_amount()

{

return amount;

}

voidoutput(ostream&strm)//выводсодержимогостекавпотокбезизвлеченияэлементов

{

node*pointer=top;

while(pointer)

{

pointer->elem.output(strm);

pointer=pointer->next;

}

}

~stack()

{

amount=0;

node*p=top;

while(p!=NULL)

{

p=top->next;

delete top;

top=p;

}

}

};

Клиентами класса являются функции main, stack_fill_console (заполнение стека с консоли), stack_fill_file (заполнение стека из бинарного файла), stack_delete (циклическое удаление элементов), stack_clear (очистка стека). В каждой из этих функций описан пользовательский интерфейс, организованный в виде меню. Для выбора необходимого пункта меню пользователь должен ввести соответствующий символ. Пустой ввод используется для возврата в главное меню. Для проверки пустого ввода служит функция enter. Функции _getline,_getunint используются для обработки исключений и сброса ошибок потока при вводе строк и целых чисел соответственно.



2.3 Контрольные примеры

Рисунок 2.1. Главное меню

Рисунок 2.2. Ввод записей с консоли



Рисунок 2.3. Циклическое удаление записей

Рисунок 2.4. Вывод записей



Рисунок 2.5. Очистка стека и вывод количества элементов



2.4 Схемы алгоритмов

Рисунок. Функция main

Рисунок. Функция stack_fill_file



Заключение

Мы с вами проделали большой путь, открывая для себя генетические алгоритмы, их, казалось бы, тривиальную и одновременно с этим гениальную идею, взятую из природы. В ходе изучения мы многократно указывали на достоинства и недостатки генетических алгоритмов. Среди наиболее значимых положительных сторон, можно отметить:

Первый случай: когда не известен способ точного решения задачи. Если мы знаем, как оценить приспособленность хромосом, то всегда можем заставить генетический алгоритм решать эту задачу.

Второй случай: когда способ для точного решения существует, но он очень сложен в реализации, требует больших затрат времени и денег, то есть, попросту говоря, дело того не стоит. Пример - создание программы для составления персонального расписания на основе техники покрытия множеств с использованием линейного программирования.

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

Наряду с генетическими алгоритмами известны и другие методы решения задач оптимизации, основанные на природных механизмах, такие как моделирование отжига (simulated annealing) и табу-поиск (taboo search). Но эффект случайности, который безусловно присутствует при решении генетическим алгоритмом, очень воодушевляет.

Несмотря на небольшое количество задач, которое мы с вами рассмотрели: как происходит применение генетического алгоритма в программировании на примере c++.



Список использованной литературы

1. Гальцына О.Л., Попов И.И. "Основы алгоритмизации и программирования".

2. Грешилов А.А. "Как принять наилучшее решение в реальных условиях", - М.: 1991 г., стр. 164-170.

3. Корнеев В.В., Гареев А.Ф. "Базы данных. Интеллектуальная обработка данных", М.: 2001 г., стр. 220.

4. Леонов О.И. "Теория графов".

5. Новиков Ф.А. "Дискретная математика для программистов".

6. Де Джонг К.А. Введение ко второму специальному выпуску по генетическим алгоритмам. Машинное обучение, №5(4), с. 351-353.

Электронные источники:

7. "Генетические алгоритмы по-русски" - http://www.chat.ru/~saisa.

8. "Нейропроект. Аналитические технологии XXI века" - http://www.neuroproject.ru.

9. "Научное издательство ТВП" - http://www.tvp.ru/mathem3.htm.

10. "Факультет вычислительной математики и кибернетики МГУ (ВМиК)" - http://cmc.cs.msu.su/labs/lvk/materials/tez_sapr99_1.html.

11. "Neural Bench Development" - http://www.neuralbench.ru/rus/theory/ genetic.htm.

12. "(EHIPS) Генетические алгоритмы" - http://www.iki.rssi.ru/ehips/ genetic.htm.

13. "SENN Генетические Алгоритмы" - http://fdmhi.mega.ru/ru/senn_ga.htm.

14. Хорева Е.В. Курсовая работа. Тема "Применение генетических алгоритмов для решения задач оптимизации". - КГПУ.: 2007 г.



Приложение 1 (программа со стеком на основе массива)

#include<iostream>

#include<fstream>

#include<conio.h>

using namespace std;

struct EMPLOYEE

{

unsigned number;

char name [30];

char FIO [30];

unsigned kolvo;

unsigned salary;

void output(ostream &strm)//вывод в поток

{

strm"endl;

strm.width(5);

strm"number"' ';

strm.width(30);

strm"name"' ';

strm.width(30);

strm"FIO"' ';

strm.width(5);

strm"kolvo"' ';

strm.width(5);

strm"salary;

}

};

class stack

{

private:

EMPLOYEE*elements;

int amount;

int max;

public:

stack(int size)

{

elements=new EMPLOYEE [size];

max=size;

amount=0;

}

bool push(EMPLOYEE&in)

{

if(amount<max)

{

elements [amount++]=in;

return true;

}

return false;

}

bool pop(EMPLOYEE&out)

{

if(amount>0)

{

out=elements [--amount];

return true;

}

return false;

}

int get_amount()

{

return amount;

}

void output(ostream &strm)//вывод содержимого стека в поток без извлечения элементов

{

for(int i=amount;i>0;i--) elements [i-1].output(strm);

}

~stack()

{

delete []elements;

}

};

void stack_fill_console(stack*st);

void stack_fill_file(stack *st);

void stack_delete(stack *st);

void stack_clear(stack *st);

bool filename(char*str,int len);

void _getline(char*str,int len);

bool _getunint(unsigned &i);

bool enter();

void main()

{

setlocale(LC_CTYPE, "Russian");

stack st(20);

cout""e - ввод записей\nf - заполнить стек из файла\nd - удаление записей\nc - очистить стек\no - вывод содержимого стека на экран\nw - вывод содержимого стека в текстовый файл\na - количество элементов в стеке\nq - выход\n";

char item;//пункт меню

while(true)//главное меню

{

cout"'>';

cin.get(item);

cin.sync();

switch(item)

{

case 'e':

stack_fill_console(&st);

break;

case 'f':

stack_fill_file(&st);

break;

case 'd':

stack_delete(&st);

break;

case 'c':

stack_clear(&st);

break;

case 'o':

st.output(cout);

cout"endl;

break;

case 'w':

{ofstream file("output.txt");

st.output(file);

file.close();

break;}

case 'a':

cout""Количество элементов: ""st.get_amount()"endl;

break;

case 'q':

return;

break;

default:cout""Неверный ввод""endl;

}

}

_getch();

}

void stack_fill_console(stack*st)

{

EMPLOYEE buf;//буфер для структур

do

{

cout"endl;

do

{

cout""Номер: ";

if(enter()) return;//проверка пустого ввода

} while (!_getunint(buf.number));//цикл повторяется, пока не будет введено верное число

cout""Название: ";

if(enter()) return;

_getline(buf.name,30);

cout""Фамилия директора: ";

if(enter()) return;

_getline(buf.FIO,30);

do

{

cout""Количество сотрудников: ";

if(enter()) return;

} while (!_getunint(buf.kolvo));

do

{

cout""Годовой доход: ";

if(enter()) return;

} while (!_getunint(buf.salary));

}while(st->push(buf));

cout""Стек переполнен""endl;

}

void stack_fill_file(stack*st)

{

char fname [255];//путь и имя файла

filename(fname,255);//ввод пути и имени

ifstream f(fname,ios_base::in);

EMPLOYEE buf;//буфер для структур

while(f.read((char*)&buf,sizeof(buf)))

if (st->push(buf))

{

cout""Стек переполнен. Не все записи были извлечены.""endl;

break;

}

f.close();

}

void stack_delete(stack *st)

{

EMPLOYEE buf;//буфер для структур

bool f=st->pop(buf);//флаг наличия элементов в стеке(0 - пуст)

bool filename_flag=false;//показывает, было ли введено имя файла (при циклическом удалении имя файла вводится только при первой попытке сохранения)

char fname [255];//путь и имя файла

cout""n - удалить следующий\nf - сохранить в файл\nr - вернуть в стек\n<enter> - выход\n";

char item;//пункт меню

while(f)

{

cout""Удаленный элемент:";

buf.output(cout);

cout"endl"""";

cin.get(item);

cin.sync();

switch(item)

{

case'n':

f=st->pop(buf);

continue;

case'f':

{

if (!filename_flag)//ввод пути и имени при первой попытке сохранения

{

if(!filename(fname,255))continue;

filename_flag=true;

}

ofstream file(fname,ios::binary|ios::app);

file.write((char*)&buf,sizeof(buf));//запись в конец файла

file.close();

continue;}

case'r':

st->push(buf);

return;

case 10:

return;

default:

cout""Неверный ввод""endl;

continue;

}

}

cout""Стек пуст""endl;

}

void stack_clear(stack *st)

{

EMPLOYEE buf;//буфер для структур

cout""y - очистить\nf - сохранить в файл\n<enter> - выход\n";

char item;//пункт меню

while(true)

{

cout""Очистить стек?""endl;

cout"""";

cin.get(item);

cin.sync();

switch(item)

{

case'y':

while(st->pop(buf)) buf.output(cout);

cout"endl;

return;

case'f':

{char fname [255];//путь и имя файла

if(!filename(fname,255)) continue;

ofstream file(fname,ios::binary|ios::app);

while(st->pop(buf)) file.write((char*)&buf,sizeof(buf));//запись в конец файла

file.close();

return;}

case 10:

return;

default:

cout""Неверный ввод""endl;

continue;

}

}

}

bool filename(char*str,int len)//ввод имени файла(true - строка введена, false - нажат enter)

{

cout""Введите путь и имя файла: ";

if (enter()) return false;

_getline(str,len);

return true;

}

void _getline(char*str,int len)//ввод строки

{

cin.getline(str,len);

if(cin.fail()) cin.clear();//сброс ошибочного состояния

cin.sync();//очистка потока

}

bool _getunint(unsigned &i)//ввод беззнакового целого(false - введено отрицательное число или ошибка потока)

{

cin"i;

if(cin.fail() || (int)i<0)

{

cin.clear();//сброс ошибочного состояния потока

cout""Ошибка ввода""endl;

cin.sync();//очистка потока ввода

return false;

}

cin.sync();

return true;

}

bool enter()//проверка нажатия enter перед получением данных из потока (true - нажат)

{

if(cin.peek()==10)//провека первого символа без его извлечения

{

cin.sync();//очистка потока ввода

return true;

}

return false



Приложение 2 (программа со стеком на основе списка)

#include<iostream>

#include<fstream>

#include<conio.h>

using namespace std;

struct EMPLOYEE

{

unsigned number;

char name [30];

char FIO [30];

unsigned kolvo;

unsigned salary;

void output(ostream &strm)//вывод в поток

{

strm"endl;

strm.width(5);

strm"number"' ';

strm.width(30);

strm"name"' ';

strm.width(30);

strm"FIO"' ';

strm.width(5);

strm"kolvo"' ';

strm.width(5);

strm"salary;

}

};

class stack

{

private:

struct node//Элемент и указатель на след. элемент

{

EMPLOYEE elem;

node*next;

}*top;//Указатель на структуры

int amount;

int max;

public:

stack(int size)

{

top=NULL;

max=size;

amount=0;

}

bool push(EMPLOYEE &in)//Помещение элемента в стек, принимает указ. на структуры

{

if(amount<max)

{

node*p=top;

top=new node;

top->elem=in;

top->next=p;

amount++;

return true;

}

return false;

}

bool pop(EMPLOYEE &out)//Извлекает

{

if(amount>0)

{

out=top->elem;

node*p=top->next;

delete top;

top=p;

amount--;

return true;

}

return false;

}

int get_amount()//Получение кол-во

{

return amount;

}

void output(ostream &strm)//вывод содержимого стека в поток без извлечения элементов

{

node*pointer=top;

while(pointer)

{

pointer->elem.output(strm);

pointer=pointer->next;

}

}

~stack()

{

amount=0;

node*p=top;

while(p!=NULL)

{

p=top->next;

delete top;

top=p;

}

}

};

void stack_fill_console(stack*st);

void stack_fill_file(stack *st);

void stack_delete(stack *st);

void stack_clear(stack *st);

bool filename(char*str,int len);

void _getline(char*str,int len);

bool _getunint(unsigned &i);

bool enter();

void main()

{

setlocale(LC_CTYPE, "Russian");

stack st(20);

cout""*******************************************************************************\n* Выберите команду для работы: &Kurshach 2015&\n* e - ввод записей\n* f - заполнить стек из файла\n* d - удаление записей\n* c - очистить стек\n* o - вывод содержимого стека на экран\n* w - вывод содержимого стека в текстовый файл\n* a - количество элементов в стеке\n* h - вызов помощи\n* q - выход\n*******************************************************************************\n";

char item;//пункт меню

while(true)//главное меню

{

cout"'>';

cin.get(item);

cin.sync();

switch(item)

{

case 'e':

stack_fill_console(&st);

break;

case 'f':

stack_fill_file(&st);

break;

case 'd':

stack_delete(&st);

break;

case 'c':

stack_clear(&st);

break;

case 'o':

st.output(cout);

cout"endl;

break;

case 'w':

{ofstream file("output.txt");

st.output(file);

file.close();

break;}

case 'a':

cout""Количество элементов: ""st.get_amount()"endl;

break;

case 'h':

cout""*******************************************************************************\n* Выберите команду для работы: &Kurshach 2015&\n* e - ввод записей\n* f - заполнить стек из файла\n* d - удаление записей\n* c - очистить стек\n* o - вывод содержимого стека на экран\n* w - вывод содержимого стека в текстовый файл\n* a - количество элементов в стеке\n* h - вызов помощи\n* q - выход\n*******************************************************************************\n";

break;

case 'q':

return;

break;

default:cout""Неверный ввод""endl;

}

}

_getch();

}

void stack_fill_console(stack*st)

{

EMPLOYEE buf;//буфер для структур

do

{

cout"endl;

do

{

cout""Номер: ";

if(enter()) return;//проверка пустого ввода

} while (!_getunint(buf.number));//цикл повторяется, пока не будет введено верное число

cout""Название: ";

if(enter()) return;

_getline(buf.name,30);

cout""Фамилия директора: ";

if(enter()) return;

_getline(buf.FIO,30);

do

{

cout""К-во сотрудников: ";

if(enter()) return;

} while (!_getunint(buf.kolvo));

do

{

cout""Годовой доход: ";

if(enter()) return;

} while (!_getunint(buf.salary));

}while(st->push(buf));

cout""Стек переполнен""endl;

}

void stack_fill_file(stack*st)

{

char fname [255];//путь и имя файла

filename(fname,255);//ввод пути и имени

ifstream f(fname,ios_base::in);

EMPLOYEE buf;//буфер для структур

while(f.read((char*)&buf,sizeof(buf)))

if (st->push(buf))

{

cout""Стек переполнен. Не все записи были извлечены.""endl;

break;

}

f.close();

}

void stack_delete(stack *st)

{

EMPLOYEE buf;//буфер для структур

bool f=st->pop(buf);//флаг наличия элементов в стеке(0 - пуст)

bool filename_flag=false;//показывает, было ли введено имя файла (при циклическом удалении имя файла вводится только при первой попытке сохранения)

char fname [255];//путь и имя файла

cout""n - удалить следующий\nf - сохранить в файл\nr - вернуть в стек\n<enter> - выход\n";

char item;//пункт меню

while(f)

{

cout""Удаленный элемент:";

buf.output(cout);

cout"endl"""";

cin.get(item);

cin.sync();

switch(item)

{

case'n':

f=st->pop(buf);

continue;

case'f':

{

if (!filename_flag)//ввод пути и имени при первой попытке сохранения

{

if(!filename(fname,255))continue;

filename_flag=true;

}

ofstream file(fname,ios::binary|ios::app);

file.write((char*)&buf,sizeof(buf));//запись в конец файла

file.close();

continue;}

case'r':

st->push(buf);

return;

case 10:

return;

default:

cout""Неверный ввод""endl;

continue;

}

}

cout""Стек пуст""endl;

}

void stack_clear(stack *st)

{

EMPLOYEE buf;//буфер для структур

cout""y - очистить\nf - сохранить в файл\n<enter> - выход\n";

char item;//пункт меню

while(true)

{

cout""Очистить стек?""endl;

cout"""";

cin.get(item);

cin.sync();

switch(item)

{

case'y':

while(st->pop(buf)) buf.output(cout);

cout"endl;

return;

case'f':

{char fname [255];//путь и имя файла

if(!filename(fname,255)) continue;

ofstream file(fname,ios::binary|ios::app);

while(st->pop(buf)) file.write((char*)&buf,sizeof(buf));//запись в конец файла

file.close();

return;}

case 10:

return;

default:

cout""Неверный ввод""endl;

continue;

}

}

}

bool filename(char*str,int len)//ввод имени файла(true - строка введена, false - нажат enter)

{

cout""Введите путь и имя файла: ";

if (enter()) return false;

_getline(str,len);

return true;

}

void _getline(char*str,int len)//ввод строки

{

cin.getline(str,len);

if(cin.fail()) cin.clear();//сброс ошибочного состояния

cin.sync();//очистка потока

}

bool _getunint(unsigned &i)//ввод беззнакового целого(false - введено отрицательное число или ошибка потока)

{

cin"i;

if(cin.fail() || (int)i<0)

{

cin.clear();//сброс ошибочного состояния потока

cout""Ошибка ввода""endl;

cin.sync();//очистка потока ввода

return false;

}

cin.sync();

return true;

}

bool enter()//проверка нажатия enter перед получением данных из потока (true - нажат)

{

if(cin.peek()==10)//провека первого символа без его извлечения

{

cin.sync();//очистка потока ввода

return true;

}

return false;

Размещено на Allbest.ru

...