from random import randint

# グローバル変数
knap_max = 6       # ナップサックの耐重量（kg）
item_num = 5       # 品物の種類
ind_num = 8        # 個体の数
mutate_rate = 10   # 突然変異する確率（10％）

# 品物の名称
item_name = ['A', 'B', 'C', 'D', 'E']    
# 品物の重量（kg）
item_weight = [1, 2, 3, 4, 5]            
# 品物の価値（円）
item_value = [100, 200, 350, 500, 650]   

ind_generation = None   # 個体の世代

# 個体の遺伝子
ind_gene = [[None] * item_num for _ in range(0, ind_num, 1)]

ind_weight = [None] * ind_num    # 個体の重量
ind_value = [None] * ind_num     # 個体の価値
ind_fitness = [None] * ind_num   # 個体の適応度

# 個体をランダムに生成する関数
def create_individual():
  global ind_num, item_num, ind_gene

  # 0か1をランダムに格納する
  for ind in range(0, ind_num, 1):
    for item in range(0, item_num, 1):
      ind_gene[ind][item] = randint(0, 1)

# 個体の重量、価値、適応度を計算する関数
def calc_individual():
  global ind_weight, ind_value, ind_gene, ind_fitness

  for ind in range(0, ind_num, 1):
    # 重量と価値を計算する
    ind_weight[ind] = 0
    ind_value[ind] = 0
    for item in range(0, item_num, 1):
      if ind_gene[ind][item] == 1:
        ind_weight[ind] += item_weight[item]
        ind_value[ind] += item_value[item]

    # 適応度を計算する
    if ind_weight[ind] <= knap_max:
      # 耐重量以下なら、価値をそのまま適応度とする
      ind_fitness[ind] = ind_value[ind]
    else:
      # 耐重量を超えているなら、適応度を0とする
      ind_fitness[ind] = 0

# 個体の情報を表示する関数
def show_individual():
  global ind_generation, ind_num, item_num, ind_gene
  global ind_fitness, ind_weight, ind_value

  # 世代を表示する
  print(f"\n＜第{ind_generation}世代＞")

  # 遺伝子、重量、価値、適応度を表示する
  print("遺伝子\t\t重量\t価値\t適応度")
  for ind in range(0, ind_num, 1):
    for item in range(0, item_num, 1):
      print(f"[{ind_gene[ind][item]}]", end="")
    print(f"\t{ind_weight[ind]:2d}kg", end="")
    print(f"\t{ind_value[ind]:4d}円\t{ind_fitness[ind]:4d}")
  print()

# 個体を適応度の大きい順にソートする関数
def sort_individual():
  global ind_num, ind_fitness, item_num, ind_gene
  global ind_weight, ind_value, ind_fitness

  # 挿入法でソートする
  for pos in range(1, ind_num, 1):
    ins = pos
    while ins >= 1 and ind_fitness[ins - 1] < ind_fitness[ins]:
      for item in range(0, item_num, 1):
        tmp = ind_gene[ins - 1][item]
        ind_gene[ins - 1][item] = ind_gene[ins][item]
        ind_gene[ins][item] = tmp

      tmp = ind_weight[ins - 1]
      ind_weight[ins - 1] = ind_weight[ins]
      ind_weight[ins] = tmp

      tmp = ind_value[ins - 1]
      ind_value[ins - 1] = ind_value[ins]
      ind_value[ins] = tmp

      tmp = ind_fitness[ins - 1]
      ind_fitness[ins - 1] = ind_fitness[ins]
      ind_fitness[ins] = tmp

      ins -= 1

# 淘汰する関数
def select_individual():
  global ind_num, item_num, ind_gene

  # 適応度の上位50％を下位50％にコピーする
  # （下位50％を淘汰する）
  for ind in range(0, ind_num // 2, 1):
    for item in range(0, item_num, 1):
      ind_gene[ind + ind_num // 2][item] = ind_gene[ind][item]
  print("下位50％を淘汰しました。")

# 交叉する関数
def crossover_individual():
  global ind_num, item_num, ind_gene

  # 下位50％にコピーした個体を対象とする
  for ind in range(ind_num // 2, ind_num - 1, 2):
    # 交叉する位置をランダムに決める
    crossover_point = randint(0, item_num - 1)
    for item in range(crossover_point, item_num, 1):
      # 隣の個体と交差する
      tmp = ind_gene[ind][item]
      ind_gene[ind][item] = ind_gene[ind + 1][item]
      ind_gene[ind + 1][item] = tmp
    print(f"個体{ind}と個体{ind + 1}を", end="")
    print(f"{crossover_point}の位置で交叉しました。")

# 突然変異する関数
def mutate_individual():
  global ind_num, item_num, ind_gene

  # 下位50％にコピーした個体を対象とする
  for ind in range(ind_num // 2, ind_num, 1):
    for item in range(0, item_num, 1):
      # あらかじめ決められた確率で突然変異する
      if randint(1, 100) <= mutate_rate:
        # 反転する
        ind_gene[ind][item] ^= 1
        print(f"個体{ind}の{item}の位置で突然変異しました。")

# プログラムの実行開始位置となるmain関数
def main():
  global ind_generation, item_num, ind_gene, item_name
  global item_weight, item_value, ind_weight, ind_value

  # 最大の世代をキー入力する
  gen_max = int(input("最大の世代 = "))

  # （1）初期の個体をランダムに8個生成する
  ind_generation = 1
  create_individual()

  # （2）個体の適応度を計算する
  calc_individual()

  # （3）適応度の大きい順にソートする
  sort_individual()

  # 個体を表示する
  show_individual()

  # 世代を進める
  ind_generation += 1
  
  # （6）指定した世代まで、（2）～（5）を繰り返す
  while (ind_generation <= gen_max):
    # （3）適応度の大きい順にソートする
    sort_individual()
    
    # （4）適応度の下位50％を淘汰するため、
    #      上位50％を下位50％にコピーする
    select_individual()
    # （5）コピーされた下位50％で交叉と突然変異を行う
    crossover_individual()
    mutate_individual()
    # （2）個体の適応度を計算する
    calc_individual()
    # （3）適応度の大きい順にソートする
    sort_individual()
    # 個体を表示する
    show_individual()
    # 世代を進める
    ind_generation += 1

  # （7）適応度が最も大きい個体を解とする
  print("＜遺伝的アルゴリズムで得られた解＞")
  for item in range(0, item_num, 1):
    if ind_gene[0][item] == 1:
      print(f"{item_name[item]},", end=" ")
      print(f"{item_weight[item]}kg,", end=" ")
      print(f"{item_value[item]}円")
  print(f"重量の合計値 = {ind_weight[0]}kg")
  print(f"価値の最大値 = {ind_value[0]}円")

# メイン関数を呼び出す
if __name__ == "__main__":
  main()