Python での遺伝的プログラミング: ナップザック問題


DALL・Eで作成した画像

この記事では、コンピューター サイエンスの古典であるナップザック問題について見ていきます。 従来の計算方法を使用して解決するのが難しい理由と、遺伝的プログラミングが「十分な」解決策を見つけるのにどのように役立つかを説明します。 その後、そのようなソリューションの Python 実装を見て、自分自身でテストします。

ナップザック問題は、複雑な計算問題を解く難しさを説明するために使用できます。 最も単純な形式では、特定の容量のナップザック、サイズと値を持つアイテムのセットが与えられ、容量を超えないようにナップザックに入れられたアイテムの値を最大化するように求められます. ナップザック問題はさまざまな方法で定式化できますが、一般に、従来のアルゴリズムを使用すると解決が難しい問題であると考えられています。

ナップザック問題の難しさは、大域的最適解を保証できる既知の解がないことを意味する NP 完全問題であることにあります。 したがって、この問題は扱いにくく、従来の方法を使用して迅速に解決することはできません。 ナップザック問題を解決するための最もよく知られているアルゴリズムは、実行時間が長くなる可能性があり、最適なソリューションを保証しない可能性があるブルート フォース検索またはヒューリスティックを使用するものです。

ただし、遺伝的プログラミングは、ナップザック問題の解決策を見つけるための代替方法を提供できます。 遺伝的プログラミングは、進化的アルゴリズムを使用して複雑な問題の解決策を探す手法です。 遺伝的プログラミングを使用すると、与えられた問題に対して「十分な」解決策をすばやく見つけることができます。 また、ソリューションの最適化と改善にも使用できます。

遺伝的プログラミングでは、一連の可能な解 (または初期生成) がランダムに生成され、一連の基準に基づいて評価されます。 次に、基準に最も適合するソリューションが選択され、遺伝子突然変異が適用されて、新しいソリューション バリアント (または後続の世代) が作成されます。 次に、この新しい世代のバリアントが評価され、満足のいく解決策が見つかるまでプロセスが繰り返されます。 このプロセスは、最適な、または最適な「十分な」ソリューションが見つかるまで繰り返されます。

ナップザック問題を解決するために遺伝的プログラミングを使用する利点は、考えられるすべての解を徹底的に検索しなくても、十分な解をすばやく見つけることができることです。 これにより、従来のアルゴリズムよりもはるかに効率的なアプローチとなり、はるかに迅速にソリューションを見つけることができます。

ナップザック問題とは何か、遺伝的プログラミングとは何か、後者を使用して前者を解決しようとする理由がわかったので、上記で説明したことの Python 実装を見てみましょう。

重要な機能を 1 つずつ見ていき、その後全体的なプログラムを見ていきます。

このプログラムは Python で実装されており、サードパーティのライブラリは使用されていません。

ランダム母集団を生成する

この関数は、指定されたサイズのランダムな母集団を生成します。 for ループを使用して指定されたサイズを反復処理し、反復ごとに染色体を作成します。 この染色体は、random.choice() 関数を使用して生成される 0 と 1 のリストです。 次に、染色体が母集団リストに追加されます。 最後に、関数はメッセージを出力し、人口リストを返します。 この関数は、遺伝的アルゴリズムの個体群を作成するのに役立ちます。

def generate_population(size):
	population = []
	for _ in range(size):
		genes = [0, 1]
		chromosome = []
		for _ in range(len(items)):
			chromosome.append(random.choice(genes))
		population.append(chromosome)
	print("Generated a random population of size", size)
	return population

染色体適合度を計算する

この関数は、染色体の適合度を計算するために使用されます。 引数として染色体を取り、それを反復処理します。 特定のインデックスの染色体の値が 1 の場合、対応するアイテムの重量と値が合計重量と合計値にそれぞれ追加されます。 合計重量が最大重量を超える場合、フィットネスは 0 に設定されます。それ以外の場合、フィットネスは合計値に設定されます。 この関数は、特定の染色体の適合性を判断するために遺伝的アルゴリズムで使用されます。

def calculate_fitness(chromosome):
	total_weight = 0
	total_value = 0
	for i in range(len(chromosome)):
		if chromosome[i] == 1:
			total_weight += items[i][0]
			total_value += items[i][1]
	if total_weight > max_weight:
		return 0
	else:
		return total_value

染色体の選択

この関数は、交差のために母集団から 2 つの染色体を選択するために使用されます。 最初に、calculate_fitness() 関数を使用して、集団内の各染色体の適合値を計算します。 次に、各値をすべてのフィットネス値の合計で割ることによって、フィットネス値を正規化します。 最後に、random.choices() 関数を使用して、正規化されたフィットネス値に基づいて母集団から 2 つの染色体をランダムに選択します。 次に、選択された 2 つの染色体が交叉の親染色体として返されます。

def select_chromosomes(population):
	fitness_values = []
	for chromosome in population:
		fitness_values.append(calculate_fitness(chromosome))
	
	fitness_values = [float(i)/sum(fitness_values) for i in fitness_values]
	
	parent1 = random.choices(population, weights=fitness_values, k=1)[0]
	parent2 = random.choices(population, weights=fitness_values, k=1)[0]
	
	print("Selected two chromosomes for crossover")
	return parent1, parent2

クロスオーバーを行う

この機能は、2 つの染色体間の交差を実行します。 2 つの親染色体を入力として受け取り、交差点をランダムに選択します。 次に、交点で 2 つの親染色体を組み合わせて、2 つの子染色体を作成します。 最初の子染色体は、最初の親染色体の最初の部分と 2 番目の親染色体の 2 番目の部分をとることによって作成されます。 2 番目の子染色体は、2 番目の親染色体の最初の部分と最初の親染色体の 2 番目の部分をとることによって作成されます。 最後に、2 つの子染色体が出力として返されます。

def crossover(parent1, parent2):
	crossover_point = random.randint(0, len(items)-1)
	child1 = parent1[0:crossover_point] + parent2[crossover_point:]
	child2 = parent2[0:crossover_point] + parent1[crossover_point:]
	
	print("Performed crossover between two chromosomes")
	return child1, child2

突然変異を実行する

この関数は、染色体の突然変異を実行します。 染色体を引数として取り、random モジュールを使用して、0 から染色体の長さまでの乱数を生成します。 突然変異点の値が 0 の場合は 1 に変更され、1 の場合は 0 に変更されます。関数はメッセージを出力し、突然変異した染色体を返します。 この関数を使用して、生物の集団における遺伝子変異をシミュレートできます。

def mutate(chromosome):
	mutation_point = random.randint(0, len(items)-1)
	if chromosome[mutation_point] == 0:
		chromosome[mutation_point] = 1
	else:
		chromosome[mutation_point] = 0
	print("Performed mutation on a chromosome")
	return chromosome

最高の染色体を取得

この関数は、染色体の母集団を取り込み、母集団から最適な染色体を返します。 これは、最初に集団内の各染色体の適合値のリストを作成することによって行われます。 次に、リスト内の最大フィットネス値とそれに対応するインデックスを見つけます。 最後に、最大適応度値のインデックスで染色体を返します。 この関数は、染色体の集団から最適な染色体を見つけて、それをさらなる操作に使用するのに役立ちます。

def get_best(population):
	fitness_values = []
	for chromosome in population:
		fitness_values.append(calculate_fitness(chromosome))

	max_value = max(fitness_values)
	max_index = fitness_values.index(max_value)
	return population[max_index]

制御ループ

このコードは、進化的アルゴリズムを実行して染色体の集団を進化させています。 指定された世代数をループすることから始めます。 世代ごとに、母集団から 2 つの染色体が選択され、それらに対して交差が実行されて 2 つの新しい染色体が生成されます。 次に、2つの新しい染色体は、一定の確率で突然変異を受けます。 ランダムに生成された確率が所定の閾値を超える場合、新しい染色体は個別にランダムな遺伝子変異を受ける。 最後に、古い集団は、2 つの新しい染色体と古い集団の残りの染色体で構成される新しい集団に置き換えられます。

for _ in range(generations):
	# select two chromosomes for crossover
	parent1, parent2 = select_chromosomes(population)

	# perform crossover to generate two new chromosomes
	child1, child2 = crossover(parent1, parent2)

	# perform mutation on the two new chromosomes
	if random.uniform(0, 1) < mutation_probability:
		child1 = mutate(child1)
	if random.uniform(0, 1) < mutation_probability:
		child2 = mutate(child2)

	# replace the old population with the new population
	population = [child1, child2] + population[2:]

上記の関数と制御ループを使用して、アイテムのリストをいくつかのパラメーターといくつかの出力と共にコンソールに追加すると、次の完全な Python 実装が得られます。

簡単にするために、すべてのパラメータがハードコードされていることに注意してください。 ただし、ほとんど問題なく、代わりにコマンドライン引数を受け入れたり、利用可能なアイテムの数、値、重量など、それらのいずれかに対するユーザー入力を求めたりすることができます.

import random

# function to generate a random population
def generate_population(size):
	population = []
	for _ in range(size):
		genes = [0, 1]
		chromosome = []
		for _ in range(len(items)):
			chromosome.append(random.choice(genes))
		population.append(chromosome)
	print("Generated a random population of size", size)
	return population

# function to calculate the fitness of a chromosome
def calculate_fitness(chromosome):
	total_weight = 0
	total_value = 0
	for i in range(len(chromosome)):
		if chromosome[i] == 1:
			total_weight += items[i][0]
			total_value += items[i][1]
	if total_weight > max_weight:
		return 0
	else:
		return total_value

# function to select two chromosomes for crossover
def select_chromosomes(population):
	fitness_values = []
	for chromosome in population:
		fitness_values.append(calculate_fitness(chromosome))
	
	fitness_values = [float(i)/sum(fitness_values) for i in fitness_values]
	
	parent1 = random.choices(population, weights=fitness_values, k=1)[0]
	parent2 = random.choices(population, weights=fitness_values, k=1)[0]
	
	print("Selected two chromosomes for crossover")
	return parent1, parent2

# function to perform crossover between two chromosomes
def crossover(parent1, parent2):
	crossover_point = random.randint(0, len(items)-1)
	child1 = parent1[0:crossover_point] + parent2[crossover_point:]
	child2 = parent2[0:crossover_point] + parent1[crossover_point:]
	
	print("Performed crossover between two chromosomes")
	return child1, child2

# function to perform mutation on a chromosome
def mutate(chromosome):
	mutation_point = random.randint(0, len(items)-1)
	if chromosome[mutation_point] == 0:
		chromosome[mutation_point] = 1
	else:
		chromosome[mutation_point] = 0
	print("Performed mutation on a chromosome")
	return chromosome

# function to get the best chromosome from the population
def get_best(population):
	fitness_values = []
	for chromosome in population:
		fitness_values.append(calculate_fitness(chromosome))

	max_value = max(fitness_values)
	max_index = fitness_values.index(max_value)
	return population[max_index]


# items that can be put in the knapsack
items = [
		[1, 2],
		[2, 4],
		[3, 4],
		[4, 5],
		[5, 7],
		[6, 9]
	]

# print available items
print("Available items:n", items)

# parameters for genetic algorithm
max_weight = 10
population_size = 10
mutation_probability = 0.2
generations = 10

print("nGenetic algorithm parameters:")
print("Max weight:", max_weight)
print("Population:", population_size)
print("Mutation probability:", mutation_probability)
print("Generations:", generations, "n")
print("Performing genetic evolution:")

# generate a random population
population = generate_population(population_size)

# evolve the population for specified number of generations
for _ in range(generations):
	# select two chromosomes for crossover
	parent1, parent2 = select_chromosomes(population)

	# perform crossover to generate two new chromosomes
	child1, child2 = crossover(parent1, parent2)

	# perform mutation on the two new chromosomes
	if random.uniform(0, 1) < mutation_probability:
		child1 = mutate(child1)
	if random.uniform(0, 1) < mutation_probability:
		child2 = mutate(child2)

	# replace the old population with the new population
	population = [child1, child2] + population[2:]

# get the best chromosome from the population
best = get_best(population)

# get the weight and value of the best solution
total_weight = 0
total_value = 0
for i in range(len(best)):
	if best[i] == 1:
		total_weight += items[i][0]
		total_value += items[i][1]

# print the best solution
print("nThe best solution:")
print("Weight:", total_weight)
print("Value:", total_value)

上記のコードをファイルに保存します knapsack_ga.py、次に入力して実行します python knapsack_ga.py.

出力例は次のとおりです。

Available items:
[[1, 2], [2, 4], [3, 4], [4, 5], [5, 7], [6, 9]]

Genetic algorithm parameters:
Max weight: 10
Population: 10
Mutation probability: 0.2
Generations: 10 

Performing genetic evolution:
Generated a random population of size 10
Selected two chromosomes for crossover
Performed crossover between two chromosomes
Performed mutation on a chromosome
Selected two chromosomes for crossover
Performed crossover between two chromosomes
Performed mutation on a chromosome
Selected two chromosomes for crossover
Performed crossover between two chromosomes
Selected two chromosomes for crossover
Performed crossover between two chromosomes
Selected two chromosomes for crossover
Performed crossover between two chromosomes
Selected two chromosomes for crossover
Performed crossover between two chromosomes
Selected two chromosomes for crossover
Performed crossover between two chromosomes
Selected two chromosomes for crossover
Performed crossover between two chromosomes
Performed mutation on a chromosome
Selected two chromosomes for crossover
Performed crossover between two chromosomes
Selected two chromosomes for crossover
Performed crossover between two chromosomes
Performed mutation on a chromosome

The best solution:
Weight: 10
Value: 14

そして、そこに行きます。 これで、遺伝的プログラミングを使用してナップザック問題を解決する方法がわかりました。 少し工夫すれば、上記のスクリプトを変更して、あらゆる種類の計算的に複雑な問題を解決し、「十分に良い」最適なソリューションを得ることができます。

読んでくれてありがとう!

この記事の一部は、GPT-3 の支援を受けてプロットおよび/または執筆されました。

マシュー・メイヨー (@mattmayo13) はデータ サイエンティストであり、重要なオンライン データ サイエンスおよび機械学習リソースである KDnuggets の編集長です。 彼の関心は、自然言語処理、アルゴリズムの設計と最適化、教師なし学習、ニューラル ネットワーク、および機械学習への自動化アプローチにあります。 Matthew は、コンピューター サイエンスの修士号とデータ マイニングの卒業証書を取得しています。 彼は kdnuggets の editor1 で連絡できます[dot]コム。

Leave a Comment

Your email address will not be published. Required fields are marked *