- Шумилов А.В. - организация работы в команде, разработка структуры проекта, частичная реализация алгоритма.
- Деменев К.О. - разработка и реализация GUI
- Иванова М.А. - частичная реализация алгоритма
Дано N вещей, каждая i-я имеет вес Wi и стоимость Ci. Необходимо заполнить рюкзак с максимальной вместимостью по весу Wmax вещами так, чтобы суммарная стоимость вещей в рюкзаке была максимальной. Можно класть несколько копий одной вещи в рюкзак.
Геном - упорядоченный набор чисел, больше или равных нуля, - представляется в виде целочисленного массива. Длина генома соответствует количеству введённых пользователем вещей для заполнения рюкзака. Порядок ввода предметов пользователем запоминается и фиксируется: значение по индексу в массиве генома определяет количество экземпляров определенной вещи.
Функция приспособленности (метрика качества) текущего потомка равняется либо суммарной стоимостей вещей, лежащих в рюкзаке, если их суммарный вес не превышает максимально допустимого; либо нулю в противном случае. Сам генетический алгоритм выглядит следующим образом:
- Случайная генерация начальной популяции из N хромосом;
- Вычисление функции приспособленности каждой особи текущего поколения;
- С помощью турнирного отбора, численностью 2, выбирается N родителей для следующего поколения;
- Внутри отобранного промежуточного поколения родителей произвольным образом выбирается пара особей для скрещивания;
- Производится равномерное скрещивание родителей с вероятностью Pc, получается сразу 2 потомка;
- Шаги 4-5 повторяются до тех пор, пока не получится поколение детей размера N;
- Производится мутация потомков с вероятностью Pm: каждый ген внутри генома мутирует с вероятностью Pg по следующей формуле: новая переменная = старая переменная ± α, знак + или – выбирается с равной вероятностью;
- Производится элитарный отбор в следующее поколение: берется 10% лучших представителей предыдущего поколения, а остальные 90% выбираются случайно;
- Шаги 2-8 повторяются до тех пор, пока на свет не будет произведено заданное число поколений M.
