1 Understanding evolutionary and genetic algorithms
: 유전 알고리즘은 진화 알고리즘의 일종이다. 진화 알고리즘이란 진화의 원리에 따라 문제를 푸는 메타 휴리스틱 최적화 알고리즘이다.
1 무작위로 개체들을 선택한다.
2 적합도 함수를 통해 그 중에서 강한 것을 찾는다.
3 선택된 개체들을 재결합하고 변이하는 과정을 거쳐 새로운 개체 집단을 생성한다.
4 이렇게 생성된 개체와 이전 세대의 개체를 경쟁해 다음 세대를 구성한다.
5 원하는 적합도 수준에 도달할 때까지 이 과정을 반복한다.
진화 알고리즘은 자연 선택의 법칙에 의해 무작위로 선택한 개체 중에서 강한 것을 찾는다.
유전 알고리즘은 진화 알고리즘으로서 휴리스틱을 이용해 비트 문자열을 찾는 방식으로 문제를 푼다. 다시 말해 각각의 개체를 문자열로 표현해 문제를 해결한다는 것이다.
2 Fundamental concepts in genetic algorithms
- 무작위성: 무작위로 샘플링하는 방식으로 비결정적인 처리 과정의 성질
- 집단: 해답이 될 가능성이 있는 개체들의 집합
- 변이: 현재 세대의 개체 중 하나 이상을 무작위로 변형해 도출한 새로운 후보
- 재결합: 부모의 특성을 결합해 자식을 만드는 행위
- 선택: 약한 개체는 제거하고 강한 개체를 선택하는 행위
3 Generating a bit pattern with predefined parameters
if __name__ == "__main__":
# Define the number of bits
num_bits = 75
# Create a toolbox using the above parameter
toolbox = create_toolbox(num_bits)
# Seed the random number generator
random.seed(7)
# Create an initial population of 500 individuals
population = toolbox.population(n=500)
# Define probabilities of crossing and mutating
probab_crossing, probab_mutating = 0.5, 0.2
# Define the number of generations
num_generations = 60
print('\nStarting the evolution process')
# Evaluate the entire population
fitnesses = list(map(toolbox.evaluate, population))
for ind, fit in zip(population, fitnesses):
ind.fitness.values = fit
print('\nEvaluated', len(population), 'individuals')
# Iterate through generations
for g in range(num_generations):
print("\n===== Generation", g)
# Select the next generation individuals
offspring = toolbox.select(population, len(population))
# Clone the selected individuals
offspring = list(map(toolbox.clone, offspring))
# Apply crossover and mutation on the offspring
for child1, child2 in zip(offspring[::2], offspring[1::2]):
# Cross two individuals
if random.random() < probab_crossing:
toolbox.mate(child1, child2)
# "Forget" the fitness values of the children
del child1.fitness.values
del child2.fitness.values
# Apply mutation
for mutant in offspring:
# Mutate an individual
if random.random() < probab_mutating:
toolbox.mutate(mutant)
del mutant.fitness.values
# Evaluate the individuals with an invalid fitness
invalid_ind = [ind for ind in offspring if not ind.fitness.valid]
fitnesses = map(toolbox.evaluate, invalid_ind)
for ind, fit in zip(invalid_ind, fitnesses):
ind.fitness.values = fit
print('Evaluated', len(invalid_ind), 'individuals')
# The population is entirely replaced by the offspring
population[:] = offspring
# Gather all the fitnesses in one list and print the stats
fits = [ind.fitness.values[0] for ind in population]
length = len(population)
mean = sum(fits) / length
sum2 = sum(x*x for x in fits)
std = abs(sum2 / length - mean**2)**0.5
print('Min =', min(fits), ', Max =', max(fits))
print('Average =', round(mean, 2), ', Standard deviation =',
round(std, 2))
print("\n==== End of evolution")
best_ind = tools.selBest(population, 1)[0]
print('\nBest individual:\n', best_ind)
print('\nNumber of ones:', sum(best_ind))4 Visualizing the progress of the evolution
if __name__ == "__main__":
# Problem size
num_individuals = 10
num_generations = 125
# Create a strategy using CMA-ES algorithm
strategy = cma.Strategy(centroid=[5.0]*num_individuals, sigma=5.0,
lambda_=20*num_individuals)
# Create toolbox based on the above strategy
toolbox = create_toolbox(strategy)
# Create hall of fame object
hall_of_fame = tools.HallOfFame(1)
# Register the relevant stats
stats = tools.Statistics(lambda x: x.fitness.values)
stats.register("avg", np.mean)
stats.register("std", np.std)
stats.register("min", np.min)
stats.register("max", np.max)
logbook = tools.Logbook()
logbook.header = "gen", "evals", "std", "min", "avg", "max" ’
# Objects that will compile the data
sigma = np.ndarray((num_generations, 1))
axis_ratio = np.ndarray((num_generations, 1))
diagD = np.ndarray((num_generations, num_individuals))
fbest = np.ndarray((num_generations,1))
best = np.ndarray((num_generations, num_individuals))
std = np.ndarray((num_generations, num_individuals))
for gen in range(num_generations):
# Generate a new population
population = toolbox.generate()
# Evaluate the individuals
fitnesses = toolbox.map(toolbox.evaluate, population)
for ind, fit in zip(population, fitnesses):
ind.fitness.values = fit ’
# Update the strategy with the evaluated individuals
toolbox.update(population)
# Update the hall of fame and the statistics with the
# currently evaluated population
hall_of_fame.update(population)
record = stats.compile(population)
logbook.record(evals=len(population), gen=gen, **record)
print(logbook.stream)
# Save more data along the evolution for plotting
sigma[gen] = strategy.sigma
axis_ratio[gen] = max(strategy.diagD)**2/min(strategy.diagD)**2
diagD[gen, :num_individuals] = strategy.diagD**2
fbest[gen] = hall_of_fame[0].fitness.values
best[gen, :num_individuals] = hall_of_fame[0]
std[gen, :num_individuals] = np.std(population, axis=0)
# The x-axis will be the number of evaluations
x = list(range(0, strategy.lambda_ * num_generations, strategy.lambda_))
avg, max_, min_ = logbook.select("avg", "max", "min")
plt.figure()
plt.semilogy(x, avg, "--b")
plt.semilogy(x, max_, "--b")
plt.semilogy(x, min_, "-b")
plt.semilogy(x, fbest, "-c")
plt.semilogy(x, sigma, "-g")
plt.semilogy(x, axis_ratio, "-r")
plt.grid(True)
plt.title("blue: f-values, green: sigma, red: axis ratio")
plt.figure()
plt.plot(x, best)
plt.grid(True)
plt.title("Object Variables")
plt.figure()
plt.semilogy(x, diagD)
plt.grid(True)
plt.title("Scaling (All Main Axes)")
plt.figure()
plt.semilogy(x, std)
plt.grid(True)
plt.title("Standard Deviations in All Coordinates")
plt.show()
+) 기호 회귀 문제 풀기, 지능형 로봇 제어기 만들기
오이