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

Исходные данные представляются с помощью массива структур e[M] ,.

где k — это стоимость предмета, а w — объем предмета.

Допустимые решения (хромосомы) представляются с помощью класса rukzak. Этот класс содержит матрицу a[M] ={0,1}, где a[i]=0 означает, что предмет не был положен в рюкзак, a[i]=1 — предмет положен в рюкзак. Поле Wn — сумма объемов генов, значение которых равно 1, т. е. сумма объемов предметов, положенных в рюкзак, высчитываемой по формуле:. Kn — значение фитнесс-функции, высчитываемой для хромосомы по формуле: .

Допустимость проверяется по формуле:

где V — максимальный объем рюкзака.

В функции rukzak* create () создается первое поколение. Начальная популяция формируется случайным образом.

Формирование репродуктивного множества В программе для отбора особей в репродуктивное множество используется турнирный отбор. Турнирный отбор — произвольно выбираются 2 разные особи, из них выбирается 1 самая сильная особь, которая попадает в репродуктивное множество. Отбор происходит до тех пор, пока в репродуктивном множестве не станет N особей. Репродуктивное множество хранится в массиве объектов класса rukzak.

Скрещивание Для скрещивания выбираются две различных особи из репродуктивного множества. Также произвольно выбирается точка разрыва.

1010 1010 1010 1111.

+ =>

• 0000 1111 0000 1010
• 10 101 010 10 1 111

+ =>

00 1 111 00 101 010.

Проверяем потомков на допустимость. Процесс повторяется до тех пор, пока не будет создано N потомков.

Мутация.

Мутировать может только один произвольный потомок. Мутирует потомок или нет, определяется произвольно. Также произвольно определяется ген потомка a[i], который подвергнется мутации. Если a[i]=0, то заменяем на a[i]=1. Если a[i]=0, то потомок не меняется.

• 1010 1 010 => 1010 0 010
• 101 0 1010 => 101 1 1010

Потомка, подверженного мутации проверяются на допустимость.

Новое поколение В новое поколение попадет часть особей из предыдущего поколения с максимальной фитнесс-функцией. А остальная часть — это самые сильные особи, получаемые в результате скрещивания и мутации. Новое поколение записывается в массив объектов класса rukzak.