import random

# 求y =-(400-x)*(400-x)+160000的最大值
# 种群初始化
def origin(number, size):
    population = []
    for i in range(number):
        temp = []
        for j in range(size):
            temp.append(random.randint(0, 1))
        population.append(temp)
    return population

# 评估适应度
def fitness(body, size):
    ten_number = 0
    count = size-1
    for i in body[0:size]:
        ten_number = ten_number + i*pow(2, count)
        count = count-1
    fit =-(400-ten_number)*(400-ten_number)+160000
    return fit

# 轮盘选择
def Select(population, size):
    total = 0
    temp = 0
    select = []
    for n in range(len(population)): select.append([])
    # select数组为二维数组，每一个数组中存放挑选的概率和选中的次数
    for i in range(len(population)):
        total = total+population[i][size]
    for j in range(len(population)):
        temp = temp + population[j][size] / total
        select[j].append(temp)
    for n in range(len(population)): select[n].append(0) #修改为A[ ,0]的形式
    for i in range(len(population)): #重复n次
        x = random.random()
        for z in range(len(select)): #修改选择的次数
            if x <= select[z][0]:
                select[z][1] = select[z][1]+1
                break
    min = max = select[0][1]
    min_num =  max_num = 0
    for i in range(len(select)):# 寻找最优个体位置
        if select[i][1] < min:
            min = select[i][1]
            min_num = i
        if select[i][1] > max:
            max = select[i][1]
            max_num = i
    return (max_num,min_num)

# 交配运算
def crossover(population, size, max_mum):
    temp_list0 = population[max_mum]
    for i in range(len(population)):
        if i == max_mum:
            population[i].pop(size)# 防止自己和自己交配
            continue
        seed = random.randint(0, size-1)
        tem_list = population[i]
        population[i] = temp_list0[0:seed] + tem_list[seed:size] # 都和最优个体交配
    return population

# 变异
def change(population, size, seed):
    for i in range(len(population)):
        if random.random() > seed:
            x = random.randint(0, size-1)
            if population[i][x] == 1:
                population[i][x] = 0
            else:
                population[i][x] = 1
    return population

number = 30
size = 10
GA_number = 100
seed = 0.01
best = 0
population = origin(number, size)
print(population)
for i in range(GA_number):
    for j in range(len(population)):
        population[j].append(fitness(population[j], size))
    (max_num, min_num) = Select(population, size)
    population[min_num] = population[max_num] #将最小选择的数组替换为最大的数组
    population = crossover(population, size, max_num)
    population = change(population, size, seed)
print(population)
for j in range(len(population)):
    population[j].append(fitness(population[j], size))
print(population)
(max_num, min_num) = Select(population, size)
best_body = population[max_num]
count = size-1
for i in best_body[0:size]:
    best = best + i * pow(2, count)
    count = count - 1
print(best)