Современные информационные технологии /1.Компьютерная  инженерия

Молдабеков М.М., Еремин Д.И., Латышев Н.В., Алиева Б.К.

ДТОО «Институт космической техники и технологий», Республика Казахстан

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

Введение

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

Сложность задачи формирования портфеля проектов экспоненциально растет с увеличением числа проектов или расширением горизонта планирования.

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

Основные положения генетического алгоритма

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

Ниже приводится алгоритм реализации данного метода.

На первом шаге из базы данных проектов задаются необходимые входные данные: наименование проекта, стоимость проекта и его ценность. Поскольку у каждого из проектов может быть только 2 статуса: включен или не включен в портфель проектов, то количество возможных вариантов будет равняться 2ⁿ, где n – количество проектов. Для ускорения дальнейших вычислений путем формирования цикла от 1 до n с шагом, равным единице, создается массив , n-й элемент которого будет равняться значению 2ⁿ. Элементы массива определяются следующим образом: при этом предварительно задано .

Создание начальной популяции реализуем путем организации цикла, условием выхода из которого будет полное заполнение массива, желаемого размера популяции. Создание особи осуществляем путем случайной генерации числа в диапазоне от 0 до 2ⁿ, и определяем суммарную ценность и полезность полученного варианта портфеля, а также соответствие ограничению по бюджету. В случае, если суммарная стоимость портфеля не превышает бюджет, то записываем данный вариант в массив популяции, затем проверяется условие: если суммарная полезность портфеля больше максимального ранее найденного значения, то данный вариант сохраняется как лучшее решение задачи. Для этого путем реализации цикла от 0 до n, в каждой итерации данного цикла в специально созданный массив для хранения лучшего найденного результата копируется значение проекта.

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

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

Далее с отобранными хромосомами осуществляем операцию скрещивания, где выбираются пары хромосом из родительской популяции. Это временная популяция, состоящая из хромосом, отобранных в результате селекции и предназначенных для дальнейших преобразований операторами скрещивания, с целью формирования новой популяции потомков. На данном этапе хромосомы из родительской популяции объединяются в пары. Это производится случайным способом в соответствии с вероятностью скрещивания. Далее для каждой пары отобранных таким образом родителей разыгрывается позиция гена (локус) в хромосоме, определяющая так называемую точку скрещивания. Если хромосома каждого из родителей состоит из L генов, то очевидно, что точка скрещивания L_k представляет собой натуральное число, меньшее L. Поэтому фиксация точки скрещивания сводится к случайному выбору числа из интервала [1,L-1]. В результате скрещивания пары родительских хромосом получается следующий потомок: потомок, хромосома которого на позициях от 1 до L_k состоит из генов хромосомы-отца, а на позициях от L_k+1 до L – из генов хромосомы-матери.

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

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

Алгоритм обработки данных реализован на языке Visual Basic.

Анализ результатов

Были проведены следующие варианты расчетов:

1. Эксперимент №1 – поиск оптимального варианта портфеля проектов методом ветвей и границ и генетическим алгоритмом.

2. Эксперимент №2 - поиск оптимального варианта портфеля проектов методом ветвей и границ и генетическим алгоритмом, при этом генетический алгоритм модифицировали, введя в него понятие элитаризма (5% лучших родительских особей переместили в популяцию потомков).

3. Эксперимент №3 - поиск оптимального варианта портфеля проектов методом ветвей и границ и генетическим алгоритмом, при этом генетический алгоритм скрестили с методом ветвей и границ (5% особей начальной популяции сгенерировали методом ветвей и границ).

В качестве начальных данных случайным образом создаем данные на 200 проектов, у каждого из проектов параметр полезности в пределах от 60 до 100, а параметр цены проекта в пределах от 20 до 200.

Результаты эксперимента №1 показаны на рисунке 1, для генетического алгоритма рассматривалась популяция из 10 000 особей. Как видно из графика, генетический алгоритм дает худшие результаты, чем метод ветвей и границ.

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

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

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

В эксперименте №3 генетический алгоритм скрестили с методом ветвей и границ, т.е. 5% особей начальной популяции сгенерировали методом ветвей и границ. Из рисунка 3 видно значительное улучшение результатов генетического алгоритма. В этом случае результаты расчетов генетическим алгоритмом намного лучше, чем методом ветвей и границ.

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

Заключение

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