Магистерский диплом на тему Применение генетических алгоритмов для решения оптимизационных задач (Распределение инвестиций внутри компании)

Содержание:

ВВЕДЕНИЕ 5
1. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ 9
1.1 Понятие инвестиции 9
1.2 Оптимизация инвестиций 10
1.3 Методы оптимизации 12
2. ГЕНЕТИЧЕСКИЙ АЛГОРИТМ 14
2.1 Естественная эволюция 14
2.2 Модели генетических алгоритмов 15
2.3 Модернизация генетических алгоритмов 21
2.4 Задача оптимизации 22
2.5 Целевая функция 25
2.6 Общая структура генетического алгоритма ……………………………………………………….25
3. ОПТИМИЗАЦИЯ РАСПРЕДЕЛЕНИЯ ИНВЕСТИЦИЙ…………………………30
3.1 Нейронная сеть и ее обучение…………………………………………………30
3.2 Оптимизация распределения инвестиций нейронной сетью……………….33
3.3 Оптимизация распределения инвестиций генетическим алгоритмом………34
4. ПРАКТИЧЕСКАЯ ЧАСТЬ ………37
4.1 Использование нейронной сети 38
4.2 Одноточечное скрещивание 39
4.3 Инверсионная мутация 40
4.4 Среда разработки………………………………………………………………..40
4.5 Анализ работ генетического алгоритма 41
4.5.1 Описание разработанной программы 41
4.5.2 Подробное описание работы программы 44
4.5.3 Полученные результаты 48
ЗАКЛЮЧЕНИЕ 53
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 54
ПРИЛОЖЕНИЯ 58
ПРИЛОЖЕНИЕ А
Программа генетического алгоритма на Pascal ABC 58
ПРИЛОЖЕНИЕ Б
Программа генетического алгоритма на Python 67
ПРИЛОЖЕНИЕ В
Результат выполнения ГА и нейросети при инвестициях по двум видам работ 83
ПРИЛОЖЕНИЕ Г
Результат выполнения ГА и нейросети при инвестициях по трем видам работ 84

Введение:

Из-за ограниченности финансовых ресурсов современное предприятие, с различными направлениями деятельности, не может принять участие в реализации долгосрочных проектов. Но существуют инвесторы, которые желают вложить средства в это современное предприятие с условием, что на выходе получат доход, превышающий их финансовый вклад. Эффективные инвестиционные решения оказывают влияние на многие показатели работы предприятия на протяжении нескольких лет.
Как быть в том случае, когда на предприятии можно, за эти финансы, обновить состав оборудования, наладить выпуск более, экономически выгодного, продукта, применить новые технологии на предприятии, что даст определенный экономический эффект и т.д.
То есть сфер приложения инвестиций много, а сумма вклада ограничена. Тогда необходимо каким-то образом распределить эти инвестиции оптимально и не во все, нуждающиеся во вложениях, работы. Как это сделать?
Оптимальным распределением инвестиций между проектами будет являться такое решение, которое обеспечит, как максимальную ожидаемую доходность при фиксированном уровне риска, так и минимальный риск при заданном уровне ожидаемой доходности. С точки зрения конечных результатов распределения инвестиционных ресурсов технический анализ должен подтвердить, что обеспечит такие ее результаты, при которых проект будет признан эффективным.
Принять правильное решение, опираясь лишь на личный опыт и интуицию, трудно. Но существуют методы управления инвестиционными программами – оптимизация. Простыми методами задачи оптимизации инвестиций порой невозможно решить или это потребует много времени и значительного объема ресурсов.
Здесь нам на помощь могут прийти программные средства и компьютерные системы. Они делают все гораздо быстрее человека, при правильно поставленной задаче, безошибочно и позволяют повысить эффективность принятия инвестиционных решений и значительно улучшить экономическую деятельность предприятия в целом.
В этом плане, в последние десятилетия, продемонстрировали свою универсальность генетические алгоритмы. Генетические алгоритмы представляют собой стохастическую оптимизационную процедуру, основанную на имитации процессов естественной эволюции: создание начальной популяции, скрещивание особей, мутации, на этой основе создание новой популяции (более приспособленных поколений) и снова повтор предыдущих действий до тех пор, пока дальнейшее применение алгоритма уже будет не целесообразно. Эти процессы в генетических алгоритмах получили название генетических операторов. В ходе работы таких алгоритмов возникает решение задачи, которое близко к оптимальному.
Генетические методы не гарантируют обнаружения глобального оптимума, но позволяет выбрать лучшее решение за меньшее время, чем другие известные алгоритмы поисковой оптимизации. Если применить генетический алгоритм для решения задачи оптимизации инвестиций, то мы получим алгоритмическое и численное решение. Это отличает его от обычных способов оптимизации и распределения инвестиций, предоставляющих только аналитическое решение и основанных на интуиции или опыте. Можно сделать вывод, что когда невозможно теоретически оценить эффективность инвестиционных решений, проводится их тщательное экспериментальное исследование и выбираются наиболее эффективные методы решения этой проблемы. Например, с помощью нейронной сети также можно оптимизировать инвестиции, но лучший вариант – гибридный. Использование нейронной сети совместно с генетическим алгоритмом может дать самый точный результат решения задачи распределения инвестиции внутри предприятия.
Объектом исследования в данной работе является оптимальное распределение инвестиций между проектами на предприятии, а предметом исследования – информационная система для нахождения оптимального инвестиционного решения с помощью нейронной сети и генетического алгоритма.
Целью данной работы является разработка программного средства, в основе которого лежит нейронная сеть и генетический алгоритм.
Методами исследования являются общенаучные методы, математические методы и объектно-ориентированное проектирование.
Главной задачей работы является нахождение глобального максимума оптимизации. Как это сделать? Для решения главной задачи рассмотрим ряд шагов, которые надо выполнить.
Задачи данной работы:
• ознакомится с распределением инвестиций между проектами на предприятии;
• рассмотреть способы и пути оптимизации;
• выбрать способ оптимизации подходящий для данного задания;
• выбрать метод отпимизации генетическим алгоритмом (в соответствии с требованиями данной работы);
• ознакомиться с моделями генетических алгоритмов;
• изучить работу нейронной сети;
• произвести, на языке программирования Python, гибридную оптимизацию по распределению инвестиций между проектами на предприятии с проведением подобной оптимизации нейронной сетью;
• сравнить оба способа оптимизации инвестиций;
• произвести анализ работы программы;
• дать свои рекомендации по распределению инвестиций внутри предприятия по проектам;
• сделать выводы.
Работа состоит из введения, четырех глав, заключения, списка использованной литературы и приложений.
Оптимизационные задачи заключаются в нахождении минимума или максимума целевой функции. Целевая функция — сложная функция, зависящая от некоторых входных параметров. Оптимизационные задачи построены так, что мы знаем целевую функцию, а надо найти значения входных параметров, при которых целевая функция достигает минимального или максимального значения.

Заключение:

В магистерской работе в теоретической части были рассмотрены вопросы понятия инвестиции, их виды и классы, распределения инвестиций на предприятии. Рассмотрен вопрос оптимизации и методы ее выполнения, вопрос существующего естественного отбора в природе, суть генетического алгоритма и модели генетических алгоритмов, работа нейронной сети.
В практической части, исходя из технического задания, проведена оптимизация распределения инвестиций, определена целевая функция и найдены максимумы, при заданных ограничениях по ῳ и k и вложенных инвестициях, для разного размера популяций и поколений.
Произведен анализ технического задания и дано определение одноточечного скрещивания и инверсной мутации. Выбран вид селекции.
Описан общий ход разработанной генетической программы и дано подробное описание процедуры скрещивания при разных популяциях и для разных поколений.
Произведен анализ полученных результатов и даны рекомендации, по каким видам работ целесообразно распределять инвестиции для получения оптимального результата (максимальной прибыли).
Составлена программа генетического алгоритма на языке PascalABC и Python. Выведено 2 результата расчета при числе поколений 30 и 100 для популяций 10, 20, 30.
Скриншот результата в Приложениях В, Г
Задание выполнено в полном объеме.

Фрагмент текста работы:

1. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ
1.1 Понятие инвестиции
Когда у нас есть набор каких-то работ, которые необходимо выполнить, но не хватает денежных средств, для их выполнения, тогда возникает задача распределения ресурсов, которые есть в наличии.
Распределить ресурсы можно по-разному. Если ресурсы ограничены, то к распределению инвестиций надо применить оптимизацию. Определяют, какой объем ресурсов можно выделить на данный вид работы в соответствии с целевой функцией и учетом ограничений на объем имеющихся ресурсов.
Выделяют три класса задач по распределению ресурсов, когда заданы:
• Работы и ресурсы. Стоит задача распределить имеющиеся ресурсы так, чтобы получить максимальную прибыль (использовать эффективность производства) или чтобы затраты ресурсов были минимальными.
• Только ресурсы. В этом случае определяем, какие работы надо выполнить под эти ресурсы, чтобы получить максимум эффективности от выполнения этих работ и обеспечить максимальный доход предприятия.
• Только работы. Здесь стоит задача минимизации суммарных издержек.
В нашем случае заданы только ресурсы и нам необходимо определить состав выполняемых работ. Оптимально распределить эти ресурсы между видами работ и получить 40% прибыли (требование инвестора).
Инвестиции – это долгосрочное вложение капитала с целью получения и наращивания дохода или инвестиции — вложение инвестором финансовых ресурсов с целью получения дополнительного дохода (прибыли).
Инвестиции классифицируются относительно объекта приложения:
• материальные инвестиции (вложение средств в имущество:запасы материалов, здания, оборудование, сооружения);
• финансовые инвестиции (покупаються ценные бумаги, облигации, акции);
• нематериальные инвестиции (средства вкладываются в рекламу, подготовку кадров, исследования и разработки).
Как эффективно будут использованы инвестиции, зависит от их структуры. Это может быть распределение на реальные (прямые) инвестиции и финансовые (портфельные) инвестиции.
Реальные инвестиции представляют собой отбор объекта инвестиций с участием самого инвестора.
Портфельные инвестиции — когда инвестор вкладывает инвестиции в ценные бумаги (акции, облигации и пр.) без свого участия в управлении и контроле над компанией, которая выпустила эти ценные бумаги.
Любое нормальное развитие экономики государства невозможно без инвестиций, которые выполняют ряд главных функций:
• развития и расширения;
• обновления основных фондов;
• повышения технического уровня производства;
• конкурентноспособности и повышения качества продукции компании;
• осуществления природоохранных мероприятий;
• приобретения ценных бумаг для вложения средств в активы других компаний;
• максимилизация прибыли и стабильность финансового состояния компании.
Рисковано вкладывать инвестиции в сферу разработок и исследований. Эта сфера инвестируется со стороны государства за счет определенных программ.
Инвестиции в большой рынок сбыта продукции всегда прибыльны (импорт продукции, нефть и газ).

1.2 Оптимизация инвестиций
Не будем рассматривать все виды оптимизации. Возьмем одну из них – пространственную и подробно разберем.
Пусть у нас есть исходные данные:
— общая сумма финансовых ресурсов на период, которая ограничена сверху;
— несколько независимых проектов с суммарным объёмом инвестиций, которые превышают финансовые ресурсы предприятия.
Составляем инвестиционный портфель для получения максимальной прибыли.
Рассмотрим варианты пространственной оптимизации, если:
• Проекты можно дробить (реализации подлежат целиком или какая-то их часть).
Используем методику анализа:
 Для каждого проекта рассчитывается индекс рентабельности.
 Проекты упорядычиваем по убыванию индекса рентабельности.
 В инвестиционный портфель включаем первых несколько проектов, которые финансируем в полном объёме.
 Если есть возможность профинансировать следующий проект, но не в полном объеме, то делаем это частино.
• Проекты не поддаются дроблению. Рассматриваем последовательно все возможные варианты сочетания проектов. Расчитываем NPV для каждого варианта.
• Временная оптимизация. Так как общая сумма финансовых ресурсов ограничена сверху и есть несколько проектов, которые не могут быть реализованы одновременно, то в этом году реализуют доступный проект, а в последующем году реализуются оставшиеся проекты или их части.
Остается тепер только оптимально распределить проекты по годам реализации.

1.3 Методы оптимизации
Оптимизация сводится к поиску наилучшего решения задачи. Делаются пробы различных решений, затем сравниваются, и рассчитывается оценка качества. Но что делать, когда число решений большое? Перебрать их невозможно, да еще различными методами решения. В этих случаях применяется оптимизация.
При поиске оптимального решения всегда определяют целевую функцию. Это главный вопрос и неправильное нахождение целевой функции приведет к не решению поставленной задачи оптимизации. Тогда находят такой набор входных данных, который минимизирует целевую функцию. Пути поиска оптимизации саме разнообразные:
• Случайный поиск – позволяет понять, чего надо достичь всем алгоритмам. Он не является одним из лучших, но может служить эталоном, с которым сравнивают другие алгоритмы.
• Алгоритм спуска с горы. Решение выбирается случайно (генерируются случайные числа) и рядом по соседству алгоритм ищет лучшее решение (меньшее значение целевой функции). Соседи текущего решения таким же образом у своих соседей ищут лучшее решение. Получается два новых списка, в одном из которых этот элемент увеличен на единицу, а в другом уменьшен на единицу. Лучшее решение становится новым решением. Такое решение не всегда является глобальным, наоборот, это локальный минимум (существенный недостаток алгоритма спуска с горы).
• Алгорит отжига начинается также с выбора случайного решения задачи. Здесь начальное значение переменной очень велико, но имеет тенденцию к понижению. На каждом этапе выбирается случайным образом один из параметров и изменяется в нужном направлении. Алгоритм может вначале принимать худшие решения, но по мере понижения переменной оно становится все лучше, и в конце работы алгоритма мы получим только лучшее решение.
• Генетический алгоритм. Создается случайный набор данных (популяция). На каждом шаге оптимизации вычисляется целевая функция. В результате получается упорядоченный список решений.
Затем мы создаем новую популяцию. Это уже будет новое поколение. Включаем в нее определенный процент самых лучших решений (элитизм), затем ищем новые решения путем модификации лучших решений.
Улучшить решения можно двумя способами: мутацией и скрещиванием.
Мутация — случайное изменение существующего решения и оно небольшое. Это либо инверсия, либо добавление 1 в один из битов популяции, либо другое решение.
Скрещиванием (или кроссовером) – это комбинация двух лучших решений. В двух лучших решениях берется случайное число элементов из одного решения, а остальные – из другого. Размер новой популяции должен совпадать с размером старой. Новую популяцию получаем путем случайных мутаций и скрещиваний лучших решений. Ее также упорядычиваем (ранжируем) и такой процесс продолжается заданное число раз до тех пор, пока не наступает никаких улучшений через определенное количество поколений. Генетический алгоритм может нам дать глобальное решение.

Заключение
В теоретической части мы ознакомились с понятием инвестиции, классами и классификацией их, эффективностью инвестиций. Также ознакомились с пространственной оптимизацией инвестиций и их видами и методами оптимизации. Это теоретический подготовительный этап магистерской работы для написания программы оптимизации инвестиций внутри предприятия.
 
2. ГЕНЕТИЧЕСКИЙ АЛГОРИТМ
2.1 Естественная эволюция
В теории Дарвина рассматривается изменение популяции биологических видов для наилучшего приспособления к окружающей среде. При переходе от поколения к поколению происходят случайные изменения отдельных материальных элементов живого организма. Эти изменения бывают разными:
• те, которые облегчают выживание и производство потомков в данной среде, сохраняются и передаются потомству (т.е. наследуются);
• которые не имеют таких характеристик и погибают, не оставив потомства или оставив его меньше, чем приспособленные (количество потомства пропорционально степени приспособленности).
Для всех членов популяции характерны индивидуальные внешние параметры (фенотип).
В каждой клетке любого живого организма содержится вся генетическая информация этой особи (генотип). Информация записана в виде набора очень длинных молекул ДНК . Каждая молекула ДНК — это цепочка, состоящая из молекул нуклеотидов четырех типов, обозначаемых: А, T, C, G. Порядок следования нуклеотидов в ДНК и составляет информацию об этой особи. Как видим, генетический код особи — это очень длинная строка символов, где используются 4 буквы. В клетке каждая молекула ДНК окружена оболочкой — хромосомой.
При рождении качество особи кодируется определенной частью хромосомы, которая называется геном, а различные значения гена называются его аллелями.
При размножении особей происходит слияние двух родительских половых клеток и их ДНК взаимодействуют, образуя ДНК потомка. Основной способ взаимодействия — кроссинговер (скрещивание). При кроссинговере ДНК предков делятся на две части и обмениваются своими половинками.
Таким образом, естественный отбор — основной механизм эволюции. Происходит конкуренция между особями популяции за различные виды ресурсов. Те особи, которые наиболее приспособлены к окружающим условиям, проживут дольше и создадут более многочисленное потомство, чем их собратья. Это означает, что гены от более адаптированных особей будут распространяться в увеличивающемся количестве потомков на каждом последующем поколении, чем менее адаптированных особей, которые или погибают, или приспосабливаются – мутируют. Иногда потомки совмещают в себе части цепи ДНК, отвечающие за наиболее удачные качества родителей. Эти особи популяции будут еще более приспособленными. Таким образом, в итоге генотип слабо приспособленных особей исчезнет из генофонда популяции.
Если в окружающей среды что-то изменяется, то иногда происходит мутация — отдельный нуклеотид цепи ДНК особи изменяется на другой нуклеотид. У потомков появляются совершенно новые качества особей популяции. Если эти новые качества полезны, они сохранятся в данном виде. Произойдет повышение приспособленности вида.
Естественный отбор, кроссинговер и мутация обеспечивают развитие популяции. Каждое новое поколение лучше удовлетворяет требованиям внешней среды, чем предыдущее, и оно будет более приспособленным.
Генетические алгоритмы моделируют процесс эволюции в природе. Таким образом, теория Дарвина применяется для решения задач оптимизации многопараметрических функций.

2.2 Модели генетических алгоритмов
Существуют следующие модели генетических алгоритмов:

Канонический генетический алгоритм. Данная модель алгоритма является классической. Она была предложена Джоном Холландом. Любая популяция состоит из N хромосом с фиксированной разрядностью генов. Производится пропорциональный отбор хромосом, формируется промежуточный массив, из которого случайным образом выбираются два родителя. Далее производится одноточечное скрещивание, и созданные два потомка мутируют с заданной вероятностью. Мутировавшие потомки занимают места своих родителей. Процесс прекращается по достижении критерия окончания алгоритма.

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

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

Гибридный алгоритм. Если сочетать генетический алгоритм с некоторым другим методом поиска, подходящим в данной задаче, то это и будет идея гибридного алгоритма. Любым методом поиска оптимума в каждом поколении все сгенерированные потомки оптимизируются, затем заносятся в новую популяцию. Тем самым получается, что каждая особь в популяции достигает локального оптимума, вблизи которого она находится. Далее производятся обычные для генетического алгоритма действия:
• отбор родительских пар;
• скрещивание;
• мутации.
На практике гибридные алгоритмы оказываются очень удачными. Это связано с тем, что вероятность попадания одной из особей в область глобального максимума велика, посколько каждая особь уже достигла локального оптимума.
После оптимизации такая особь будет являться решением задачи.

СНС. Данный алгоритм довольно быстро сходится. Это происходит потому, что в нем нет мутаций, а только скрещивание. Здесь используются популяции в малых объемах. В следующее поколение ведется скрещивание и между родительскими особями, и между их потомками. Для скрещивания выбирается случайная пара таким образом, чтобы между родителями было маленькое хеммингово расстояние или мало расстояние между крайними различающимися битами. Когда происходит скрещивание, то каждому потомку переходит ровно половина битов каждого родителя (используется разновидность однородного кроссовера). Далее, для нового поколения выбираются N лучших различных особей среди родителей и детей (дублирование строк не допускается).
Эта модель генетического алгоритма применяется при относительно малом размере популяции — около 50 особей. Это оправдывает использование однородного кроссинговера и позволяет алгоритму сойтись к решению. При получении одинаковых строк СНС применяется следующее: все строки, кроме самой приспособленной, подвергаются сильной мутации (изменяется около трети битов). Таким образом, алгоритм перезапускается и далее продолжает работу, применяя только скрещивание.

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

Некоторые модели генетических алгоритмов применяются только при параллельных вычислениях. Вот некоторые из них:
• миграция;
• Рабочий и Хозяин;
• островная.
Миграция. Генетический алгоритм представляет популяцию, как множество подпопуляций. Формируется несколько живущих отдельно популяций. На этапе формирования нового поколения, по некоторому правилу, отбираются особи из разных популяций. Созданные популяции заменяет все остальные. Особи с одной популяции как бы мигрируют в другие популяции.
Каждая подпопуляция обрабатывается отдельным процессором. Эти подпопуляций развиваются независимо друг от друга в течение одинакового количества поколений. По истечении времени изоляции, происходит обмен особями между подпопуляциями (миграция). Частоту возникновения генетического многообразия и обмен информацией между популяциями регулирует:
• количество особей, подвергшихся обмену (вероятность миграции);
• сам метод отбора особей для миграции;
• схема миграции.
Отбор особей для миграции может происходить следующим образом:
• случайная однообразная выборка из числа особей;
• пропорциональный отбор (для миграции берутся наиболее пригодные особи).
Существуют следующие схемы миграционного отбора:
• пропорциональный;
• топология кольца.
При пропорциональном отборе сначала формируется массив из наиболее пригодных особей, отобранных по всем подпопуляциям. Случайным образом из этого массива выбирается особь, которой заменяют наименее пригодную особь в подпопуляции. Аналогичные действия проделываем с остальными подпопуляциями. Иногда случается получение дубликата «хорошей» особи.
При топологии кольца особи передаются между соседними особями (по направлению обхода) подпопуляциями. Таким образом, особи из одной подпопуляций могут мигрировать только в одну — соседнюю подпопуляцию.

«Рабочий и Хозяин». Это глобальная модель генетического алгоритма. Реализуется с применением нескольких одновременно работающих компьютеров. Среди всех компьютеров выделяют «Хозяина» и «Рабочих». Компьютеры — «Рабочие» отвечают за процессы воспроизводства, мутации и вычисления функции пригодности особей для их отбора в новое поколение. Все созданные и оцененные «Рабочими» особи поступают к компьютеру — «Хозяину», который затем проводит отбор особей согласно оценке их пригодности в новую популяцию. Отобранные особи передаются «Хозяином» к компьютерам — «Рабочим».

Островная. Является наиболее распространенной моделью параллельного генетического алгоритма. Ее суть заключается в том, что популяция из большого числа особей разбивается на одинаковые по размеру подпопуляции. С помощью разновидности непараллельного генетического алгоритма каждая подпопуляция обрабатывается отдельным процессором. Иногда (через пять поколений или больше), подпопуляции обмениваются несколькими особями. Такие миграции позволяют подпопуляциям совместно использовать генетический материал.
Исследования подтверждают, что генетический дрейф склонен приводить подпопуляции к различным доминирующим особям. Это связано с тем, что:
• количество островов, которые принимают лучших особей с острова, ограничено (2-5);
• обмен особями одностороний.
В большой популяции появятся группы островов с различными доминирующими особями. Если популяция небольшого размера, то возможна быстрая миграция ложных доминирующих особей. Правильное решение находится только на одном острове. При миграции количество ложных особей на островах возрастет (на каждый остров миграции происходят с не менее 2 островов). Таким образом, верное решение генетическим алгоритмом может быть разрушено.
Островной алгоритм при маленьких популяциях применять нецелесообразно, так как происходит схождение алгоритма к ложному оптимуму.
Ввод миграций в островную модель позволяет находить различные особи, доминирующие в подпопуляциях, что способствует поддержанию многообразия в популяции. Можно принять за остров каждую подпопуляцию. Обмен своим доминирующим генетическим материалом, во время миграции, приводит к перемешиванию генетического материала. Тем самым устраняются локальные различия между островами. Каждый остров оказывается почти изолированным. Количество островов, на которые могут мигрировать особи одной подпопуляции, называют расстоянием изоляции. Взаимные миграции исключены.

2.3 Модернизация генетических алгоритмов
Преждевременная сходимость генетических алгоритмов является серьезной проблемой для любого алгоритма.
Не рекомендуется использовать классические генетические алгоритмы и островные на маленьких популяциях, потому что в популяциях с малым размером гены распространяются слишком быстро и все особи вырождаются, становятся похожими еще до того, как будет найдено решение задачи. Менее хорошие комбинации генов вытесняются новым генотипом с лучшей оценкой, исключая возможность получения лучшего решения на их базе. Предлагается три основных пути устранения преждевременной сходимости:
• увеличение размера популяции;
• применение самоадаптирующихся генетических операторов;
• создание «банка» заменяемых особей.
В первом случае можно достичь многообразия генотипа в популяции, увеличив размер популяции. Но это, увеличение числа особей, влечет за собой увеличение занимаемой памяти и времени работы алгоритма. Такой подход к решению проблемы эффективен или при параллельных вычислениях, или при наличии простой целевой функции.
Применение самоадаптирующихся алгоритмов является самым распостраненным. Самоадаптация заключается в применении динамических мутаций. Динамическая мутация способна менять значение вероятности мутации, в зависимости от скрещивающихся особей, что вызывает самоуправление алгоритмом. Малый размер популяции в этом случае предпочтителен.
Способы организации самоадаптирующегося алгоритма:
Неоднородная мутация. Если мутирует ген, то новое значение случайно генерируется на отрезке от mini, до maxi.
Инцест. Используется как механизм самоадаптации оператора мутации. Вероятность мутации каждого гена определяется для каждого потомка на основании генетической близости его родителей (отношение числа совпадающих генов родителей к общему числу генов хромосомы). Вначале инцест способствует тому, что вероятность мутации будет мала и, практически, будет происходить лишь скрещивание. При уменьшении разнообразия генофонда популяции, возникающего в случае попадания алгоритма в локальный оптимум, вероятность мутации возрастет. При полном схождении популяции алгоритм вероятности выхода популяции из локального оптимума возрастет.
Создание массива для сохранения особей применяется, когда при формировании новых поколений потерялся генотип. Временами эти особи добавляются в популяции.

2.4 Задача оптимизации
Генетический алгоритм быстро находит во всей области поиска хорошие решения. Как из этих лучних решений получить наилучшее? Здесь уже возникают трудности.
Нахождение глобального максимума является нашей задачей оптимизации. Для нахождения глобального максимума используем гибридный алгоритм. Сочетание генетического алгоритма с другим методом поиска – основная идея гибридных алгоритмов. В каждом поколении все сгенерированные потомки оптимизируются выбранным методом и затем заносятся в новую популяцию. Тем самым получается, что каждая особь в популяции достигает локального оптимума, вблизи которого она находится. Далее производятся обычные для генетического алгоритма действия: отбор родительских пар, скрещивание и мутации. На практике гибридные алгоритмы оказываются очень удачными. Это связано с тем, что вероятность попадания одной из особей в область глобального максимума обычно велика. После оптимизации такая особь будет являться решением задачи.
Сочетание двух алгоритмов позволяет использовать преимущества обоих.
В нашей работе — использование нейронной сети и генетического алгоритма. С помощью нейронной сети можно определить виды работ, в которые надо вложить инвестиции и сумму вклада в каждый вид работы, а также определить целевую функцию – прибыль. Найти локальные максимумы.
Используя генетический алгоритм, определяем целевую функцию и находим глобальный максимум.
Можно выделить следующие этапы оптимизации генетического алгоритма:
1. Задать целевую функцию (приспособленности) для особей популяции
2. Создать начальную популяцию
(Начало цикла)
3. Скрещивание
4. Мутация
5. Вычисление значения целевой функции для всех особей
6. Формирование нового поколения (селекция)
7. Если выполняются условия остановки, то (конец цикла), иначе (начало цикла).

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

Отбор (селекция)
На этом этапе нужно из всей популяции выбрать определённую её долю, которая останется «в живых» на этом этапе эволюции. Есть разные способы проводить отбор. Вероятность выживания особи должна зависеть от значения функции приспособленности и ее задают заранее. По итогам отбора из особей популяции должны остаться те, у которых функция приспособленности наибольшая и они войдут в итоговую популяцию.
Виды селекции:
• Турнирная селекция — сначала случайно выбирается установленное количество особей (обычно две), а затем из них выбирается особь с лучшим значением функции приспособленности.
• Метод рулетки — вероятность выбора особи тем вероятнее, чем лучше её значение функции.
• Метод ранжирования — вероятность выбора зависит от места в списке особей, отсортированном по значению функции приспособленности.
• Равномерное ранжирование — вероятность выбора особи определяется выражением.
• Сигма-отсечение — для предотвращения преждевременной сходимости генетического алгоритма используются методы, масштабирующие значение целевой функции. Вероятность выбора особи тем больше, чем оптимальнее значение масштабируемой целевой функции.

Выбор родителей
Размножение в генетических алгоритмах требует для производства потомка нескольких родителей, обычно двух.
Можно выделить несколько операторов выбора родителей:
• Панмиксия — оба родителя выбираются случайно, каждая особь популяции имеет равные шансы быть выбранной.
• Инбридинг — первый родитель выбирается случайно, а вторым выбирается такой, который наиболее похож на первого родителя.
• Аутбридинг- первый родитель выбирается случайно, а вторым выбирается такой, который наиболее не похож на первого родителя.
Инбридинг и аутбридинг бывают в двух формах: фенотипной и генотипной. В случае фенотипной формы похожесть измеряется в зависимости от значения функции приспособленности (чем ближе значения целевой функции, тем особи более похожи), а в случае генотипной формы похожесть измеряется в зависимости от представления генотипа (чем меньше отличий между генотипами особей, тем особи больше похожие).

Размножение (Скрещивание)
Размножение в разных алгоритмах определяется по-разному. Оно зависит от представления данных. Главное требование к размножению — потомок или потомки должны иметь возможность унаследовать черты обоих родителей, «смешав» их каким-либо способом.
Особи для размножения обычно выбираются из всей популяции, а не из выживших на первом шаге элементов. Главный недостаток многих генетических алгоритмов — отсутствие разнообразия в особях. Достаточно быстро выделяется один — единственный генотип, который представляет собой локальный максимум, а затем все элементы популяции проигрывают ему отбор, и вся популяция «забивается» копиями этой особи. Есть разные способы борьбы с таким нежелательным эффектом. Один из них — выбор для размножения не самых приспособленных, а из всех особей. Однако такой подход вынуждает хранить всех существовавших ранее особей, что увеличивает вычислительную сложность задачи. Поэтому часто применяют методы отбора особей для скрещивания таким образом, чтобы «размножались» не только самые приспособленные, но и другие особи, обладающие плохой приспособленностью. При таком подходе для разнообразия генотипа возрастает роль мутаций.
 
Мутации
К мутациям относится все то же самое, что и к размножению. На шаге мутаций нужно выбрать особей, а затем изменить их в соответствии с заранее определёнными операциями мутации. Их должно быть немного.