Анализ вариантов решения задачи

Министерство образования и науки

Томский государственный университет систем управления и

Радиоэлектроники

Кафедра автоматизации обработки информации

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

по дисциплине «Информатика (КП)»

учебное пособие Тимченко С.В.

Выполнил студент

гр. з-402-б

специальности 080500.62

Селигеев Александр Сергеевич

Оглавление

Введение

1. Анализ вариантов решения задачи

2. Описание и обоснование выбранного варианта решения

3. Результаты эксперимента

Выводы и рекомендации по результатам работы

Заключение

Приложение

Введение

Данная курсовая работа рассчитана на изучение студентом методов решения сложных задач роста популяции и мутации средствами языка программирования высокого уровня Borland Pascal.

Задание варианта:

популяция программирование алгоритм pascal

Рассмотреть одноточечное скрещивание и двухточечную мутацию.

Каждая переменная кодируется 30 битами.

Провести расчеты для 30 и 100 поколений.

Сравнить получающиеся решения при размерах популяции 10,20,30 особей.

1. Анализ вариантов решения задачи

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

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

потомок, хромосома которого на позициях от до состоит из генов первого родителя, а на позициях от до - из генов второго родителя;

потомок, хромосома которого на позициях от до состоит из генов второго родителя, а на позициях от до - из генов первого родителя.

Действие оператора скрещивания проиллюстрировано следующим примером.

Двухточечное скрещивание - отличается от точечного скрещивания тем, что родительские хромосомы обмениваются участком генетического кода, который находится между двумя случайно выбранными точками скрещивания.

Многоточечное скрещивание представляет собой обобщение предыдущих операций и характеризуется соответственно большим количеством точек скрещивания. Например, для трех точек скрещивания, равных 4, 6 и 9, и для тех же родителей, что на рисунке выше, результаты будут следующие.

Для четырех точек скрещивания, равных 4, 6, 9 и 11 можно привести такой пример.

Аналогично производится скрещивание для пяти или большего количества точек. Очевидно, что одноточечное скрещивание может считаться частным случаем многоточечного скрещивания.

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

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

2. Описание и обоснование выбранного варианта решения

Оператор скрещивание (crossover) осуществляет обмен частями хромосом между двумя (может быть и больше) хромосомами в популяции. Может быть одноточечным или многоточечным. Одноточечный кроссовер работает следующим образом. Сначала, случайным образом выбирается одна из l-1 точек разрыва. Точка разрыва - участок между соседними битами в строке. Обе родительские структуры разрываются на два сегмента по этой точке. Затем, соответствующие сегменты различных родителей склеиваются и получаются два генотипа потомков.

Мутация

Мутация (mutation) - стохастическое изменение части хромосом. Строке, которая подвергается мутации, каждый бит с вероятностью Pmut (обычно очень маленькой) меняется на другой.

Алгоритм работы ГА

Работа ГА представляет собой итерационный процесс, который продолжается до тех пор, пока не выполнятся заданное число поколений или какой-либо иной критерий останова. На каждом поколении ГА реализуется отбор пропорционально приспособленности, кроссовер и мутация.

Алгоритм работы простого ГА выглядит следующим образом:

3. Результаты эксперимента

Основные переменные, используемые при реализации алгоритма

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

Основные подпрограммы:

Function rnd(low,high:Integer):Integer; {- cлучайный выбор между low и high}

Procedure decode(chrom:chromosome; lbits:Integer; Var x:fenotype);

{- декодирование строки в массив вещественных координат точки в пространстве поиска - true=1, false=0}

Procedure statistics(popsize:Integer; Var max,avg,min,sumfitness:Real; Var pop:population); {*** Расчет статистических величин ***}

{*** Процедура инициализации (инициализация начальной популяции случайным образом) ***}

Procedure initpop;

Procedure select; {- процедура отбора}

Procedure generation;

{- генерирование нового поколения при помощи отбора, скрещивания и мутации}

{Прим.: предполагается, что популяция имеет четный размер}

Результат выполнения программы :

При 50 поколениях и размере популяции 10 особей

среднее значение минимума функции в заданной области 0.084571793507888

Наилучшее значение минимума функции в заданной области 0.000443960465983

::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::

При 50 поколениях и размере популяции 20 особей

среднее значение минимума функции в заданной области 0.102085411779220

Наилучшее значение минимума функции в заданной области 0.000443960465983

::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::

При 50 поколениях и размере популяции 30 особей

среднее значение минимума функции в заданной области 0.157094040787855

Наилучшее значение минимума функции в заданной области 0.000443960465983

::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::

При 100 поколениях и размере популяции 10 особей

среднее значение минимума функции в заданной области 0.139601413202977

Наилучшее значение минимума функции в заданной области 0.000443960465983

::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::

При 100 поколениях и размере популяции 20 особей

среднее значение минимума функции в заданной области 0.095127753861539

Наилучшее значение минимума функции в заданной области 0.000397285517399

::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::

При 100 поколениях и размере популяции 30 особей

среднее значение минимума функции в заданной области 0.162433199925989

Наилучшее значение минимума функции в заданной области 0.000397285517399

::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::

Для завершения программы нажмите ENTER

Заключение

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

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

Список использованных источников:

1. Антамошкин А.Н. Оптимизация функционалов с булевыми переменными. - Томск: Изд-во Том. ун-та, 1987, - 104 с.

2. Вороновский Г.К., и др. Генетические алгоритмы, искусственные нейронные сети и проблемы виртуальной реальности. Х.: ОСНОВА, 1997.

3. Гринченко С.Н. Метод «проб и ошибок» и поисковая оптимизация: анализ, классификация, трактовка понятия «естественный отбор». Электронный журнал «Исследовано в России», 2003.

4. Заенцев И.В. Нейронные сети: основные модели. - Учеб. пособие к курсу «Нейронные сети», ВГУ, Воронеж, 1999.

5. Карманов В.Г. Математическое программирование // БСЭ, т.15. М.: Советская энциклопедия, 1974.

6. Мануйлов В.Г. Разработка программного обеспечения на Паскале. Под редакцией и с предисловием А.И.Китова.- М.:"ПРИОР", 1996.- 238с.

Приложение 1

Код программы