# Introduction

A series of optimization algorithm implementations. First look at Overview.

The whole code can be found on github.

# problem

The implemented issues are:

# OneMax problem

The problem is to maximize the sum in an N-dimensional array with a value of 0 or 1. The highest value is when all are 1.

Example for 4 dimensions: [0, 1, 1, 0] → 2

range
Input size N \geqq 1
Range of input values 0 \leqq x_i \leqq 1
Evaluation value Sum of values ​​rounded off
Maximum evaluation value(Optimal solution) Prob(1 , \cdots , 1)=N
• Graph when the input is one-dimensional

• Graph when input is 2D

## Program code

``````class OneMax():
def __init__(self, size):
self.size = size
self.MIN_VAL = 0
self.MAX_VAL = 1
self.SCORE_MIN = 0
self.SCORE_MAX = size

def init(self):
pass

def eval(self, arr):
t = [int(x+0.5) for x in arr]  #Rounding
return sum(t)
``````

# Traveling salesman problem

When traveling to multiple cities, the question is in what order the travel distance will be the shortest.

range
City location 2D(x,y)Arranged with random numbers between 0 and 1 at the coordinates of
Input size N \geqq 2
Range of input values 0 \leqq x_i \leqq 1
Evaluation value Negative value of the distance traveled (invert the sign because we want to find the minimum value)
Maximum evaluation value(Optimal solution) unknown(Better closer to 0)
• The first starting point is from (0,0)

Regarding the input, the index of the array and the index of the city correspond, and the cities with the smallest input values ​​are turned in order. For example, if there are three cities (A, B, C) and the input is [0.3, 0.1, 0.2], the order of rotation is (0,0) → B → C → A.

• Drawing example

## Program code

``````import math
class TSP():
def __init__(self, size):
self.size = size
self.MIN_VAL = 0
self.MAX_VAL = 1
self.SCORE_MIN = -(math.sqrt(1+1) * size)
self.SCORE_MAX = 0

def init(self):
#Randomly create city locations
self.towns = [
{
"x": random.random(),
"y": random.random()
} for _ in range(self.size)
]

def eval(self, arr):
score = 0

#Get the index of the input sorted by the input value
tmp = [(i, x) for i, x in enumerate(arr)]
tmp = sorted(tmp, key=lambda x: x[1])

for i in range(len(tmp)):
if i == 0:
#Initially 0,Start from 0
town = {"x":0, "y":0}
else:
town = self.towns[tmp[i-1][0]]
next_town = self.towns[tmp[i][0]]

#The distance traveled is the score
d = abs(town["x"] - next_town["x"])
d += abs(town["y"] - next_town["y"])
score += d

#I want to find the minimum, so I invert the sign
return -score
``````

# Eight queens

The problem is to put eight queens on an 8x8 chess board. However, the queens should not be worn vertically, horizontally or diagonally. Although it is set to 8, it can be expanded when there are N pieces.

The solution for 4 queens is:

□□■□ ■□□□ □□□■ □■□□

range
Board size M \geqq 4
Input size N=M×2（(x,y)Arrange the two-dimensional array of
Range of input values 0 \leqq x_i \leqq M(Coordinates in the square)
Evaluation value Number of unique queens
Maximum evaluation value(Optimal solution) M

Although it is an input, it is a one-dimensional array in which the x and y coordinates of each queen are arranged. For example, [0, 0, 1, 2, 2, 1] means that there are three queens at (0,0) (1,2) (2,1).

## Program code

``````class EightQueen():
def __init__(self, size):
self.size = size
self.MIN_VAL = 0
self.MAX_VAL = size
self.SCORE_MIN = 0
self.SCORE_MAX = size

def init(self):
pass

def eval(self, arr):
arr = [int(x+0.5) for x in arr]  #Rounding

#Convert to coordinates
koma_list = []
for i in range(0, len(arr), 2):
koma_list.append((arr[i], arr[i+1]))

score = 0
for i in range(len(koma_list)):
f = True
for j in range(len(koma_list)):
if i==j:
continue
# x
if koma_list[i][0] == koma_list[j][0]:
f = False
break
# y
if koma_list[i][1] == koma_list[j][1]:
f = False
break
#Diagonal
ax = abs(koma_list[i][0] - koma_list[j][0])
ay = abs(koma_list[i][1] - koma_list[j][1])
if ax == ay:
f = False
break
if f:
score += 1

return score
``````

# Life game

It's a life game. It's a game that imitates the life and death of cells.

The rule is that there is an N × N board, and each cell has a state of 1 (life) and 0 (death). These cells repeat life and death under the following conditions as time progresses.

1. Birth: If there are exactly three living cells adjacent to a dead cell, the next generation will be born.
2. Survival: If there are two or three living cells adjacent to a living cell, it will survive in the next generation.
3. Depopulation: If there is less than one living cell adjacent to a living cell, it will die due to depopulation.
4. Overcrowding: If there are 4 or more living cells adjacent to a living cell, it will die due to overcrowding.
range
Board size M \geqq 2
Input size N=M×M(Arrange the squares of the two-dimensional board in one dimension)
Range of input values 0 \leqq x_i \leqq 1
Evaluation value Total number of living cells
Maximum evaluation value(Optimal solution) Unknown (value close to M × M)

In the evaluation, the number of surviving cells after X turns (max_turn) have passed is used as the evaluation value.

## Program code

``````class LifeGame():
def __init__(self, size, max_turn):
self.field_size = size
self.max_turn = max_turn
self.MIN_VAL = 0
self.MAX_VAL = 1
self.SCORE_MIN = 0
self.SCORE_MAX = size*size

def init(self):
pass

def eval(self, arr):
arr = [int(x+0.5) for x in arr]  #Rounding

#From 1D to 2D
cells = []
for y in range(self.field_size):
d = []
for x in range(self.field_size):
d.append(arr[y*self.field_size + x])
cells.append(d)

#update
for _ in range(self.max_turn):
cells = self._step(cells)

#Get the total
n = 0
for y in range(self.field_size):
for x in range(self.field_size):
n += cells[y][x]
return n

def _step(self, cells):
#Initialize once with 0
next_cells = [[ 0 for _ in range(field_size)] for _ in range(self.field_size)]

for y in range(self.field_size):
for x in range(self.field_size):
n = 0
n += self._get(cells, x-1, y-1)
n += self._get(cells, x  , y-1)
n += self._get(cells, x+1, y-1)
n += self._get(cells, x+1, y)
n += self._get(cells, x-1, y)
n += self._get(cells, x-1, y+1)
n += self._get(cells, x  , y+1)
n += self._get(cells, x+1, y+1)
if self._get(cells, x, y) == 0:
if n == 3:
next_cells[y][x] = 1
else:
if n == 2 or n == 3:
next_cells[y][x] = 1
else:
next_cells[y][x] = 0

return next_cells

def _get(self, cells, x, y):
if x < 0:
return 0
if y < 0:
return 0
if x >= self.field_size:
return 0
if y >= self.field_size:
return 0
return cells[y][x]

``````

2048

An open source game created by Italian Gabriele Chillli.

Reference: https://ja.wikipedia.org/wiki/2048_(%E3%82%B2%E3%83%BC%E3%83%A0)

Numbers are randomly placed on the 4x4 squares, and you can slide all the squares at the same time on either the top, bottom, right, or left. If the same numbers overlap when you slide, the numbers will be added. The goal is to make 2048 tiles.

range
Input size N(Number of turns)
Range of input values 0 \leqq x_i \leqq 3(Command on turn)
Evaluation value Maximum square number
Maximum evaluation value(Optimal solution) unknown

The input size is the number of turns, and the action performed in that turn is the input value. The action was decided as follows. 0: Slide up 1: Slide to the right 2: Slide down 3: Slide to the left

## Program code

``````class g2048():
def __init__(self, max_turn):
self.MIN_VAL = 0
self.MAX_VAL = 3
self.SCORE_MIN = 0
self.SCORE_MAX = float('inf')

self.max_turn = max_turn

def init(self):
#Initial field
self.fields = [[0 for _ in range(4)] for _ in range(4)]
for _ in range(2):
self.fields[random.randint(0, 3)][random.randint(0, 3)] = 2

#Random numbers to be generated are fixed with init
self.create_pos = []
for _ in range(self.max_turn):
self.create_pos.append((random.randint(0, 3), random.randint(0, 3)))

def eval(self, arr):
arr = [int(x+0.5) for x in arr]  #Rounding

#Copy initial field
fields = [ x[:] for x in self.fields]

#Run for turn
for i in range(self.max_turn):

#update
for y in range(4):
for x in range(4):
self._move(fields, arr[i], x, y)

#Install a new 2 and see the next cell if already
pos = self.create_pos[i]
x = pos[0]
y = pos[1]
for _ in range(4*4):
if fields[y][x] == 0:
fields[y][x] = 2
break
x += 1
if x >= 4:
x = 0
y += 1
if y >= 4:
y = 0

#Maximum score on the last board
score = 0
for y in range(4):
for x in range(4):
if score < fields[y][x]:
score = fields[y][x]

return score

def _move(self, fields, cmd, x, y):
if fields[y][x] == 0:
return

if cmd == 0:  # up
if y == 0:
return
tx = x
ty = y-1
elif cmd == 1:  # right
if x == 3:
return
tx = x+1
ty = y
elif cmd == 2:  # down
if y == 3:
return
tx = x
ty = y+1
elif cmd == 3:  # left
if x == 0:
return
tx = x-1
ty = y
else:
raise ValueError()

if fields[ty][tx] == 0:
#Move because the target is open
fields[ty][tx] = fields[y][x]
fields[y][x] = 0
self._move(fields, cmd, tx, ty)
elif fields[ty][tx] == fields[y][x]:
#Synthesized because they are the same number
fields[ty][tx] += fields[y][x]
fields[y][x] = 0

``````

# Benchmark function

See Benchmark Function Summary for Evaluating Optimization Algorithms for mathematical formulas. Only graphs and codes will be introduced.

• The formula is multiplied by -1 to maximize the value.

Ackley function

• One-dimensional graph

• 2D graph

• Program code
``````import math
class function_Ackley():
def __init__(self, size):
self.size = size
self.MIN_VAL = -32.768
self.MAX_VAL = 32.768
self.SCORE_MIN = -float('inf')
self.SCORE_MAX = 0

def init(self):
pass

def eval(self, arr):
sum1 = sum([x**2 for x in arr])
sum2 = sum([math.cos(2*math.pi*x) for x in arr])
n = len(arr)

score = 20 - 20 * math.exp(-0.2 * math.sqrt(sum1/n)) + math.e - math.exp(sum2/n)
return -score

``````

Griewank function

• One-dimensional graph

• 2D graph

• Program code
``````import math
class function_Griewank():
def __init__(self, size):
self.size = size
self.MIN_VAL = -600
self.MAX_VAL = 600
self.SCORE_MIN = -float('inf')
self.SCORE_MAX = 0

def init(self):
pass

def eval(self, arr):
sum1 = sum([x**2 for x in np_arr])
prod = 1
for i, x in enumerate(np_arr):
prod *= math.cos( x / math.sqrt(i+1) )
n = 1 + (sum1 - prod) / 4000
return -n
``````

Michalewicz function

• One-dimensional graph

• 2D graph

• Program code
``````import math
class function_Michalewicz():
def __init__(self, size):
self.size = size
self.MIN_VAL = 0
self.MAX_VAL = math.pi
self.SCORE_MIN = -float('inf')
self.SCORE_MAX = 0

def init(self):
pass

def eval(self, arr):
n = -sum([math.sin(x) * math.sin((i+1)*(x**2)/math.pi)**(2*10) for i,x in enumerate(np_arr)])
return -n
``````

Rastrigin function

• One-dimensional graph

• 2D graph

• Program code
``````import math
class function_Rastrigin():
def __init__(self, size):
self.size = size
self.MIN_VAL = -5.12
self.MAX_VAL = 5.12
self.SCORE_MIN = -float('inf')
self.SCORE_MAX = 0

def init(self):
pass

def eval(self, arr):
n = sum([x**2 - 10 * math.cos(2*math.pi*x) for x in np_arr])
return -( 10*self.size + n)
``````

Schwefel function

• One-dimensional graph

• 2D graph

• Program code
``````import math
class function_Schwefel():
def __init__(self, size):
self.size = size
self.MIN_VAL = -500
self.MAX_VAL = 500
self.SCORE_MIN = -float('inf')
self.SCORE_MAX = 0

def init(self):
pass

def eval(self, arr):
n = sum([x * math.sin(math.sqrt(abs(x))) for x in np_arr])
return n
``````

StyblinskiTang function

• One-dimensional graph

• 2D graph

• Program code
``````import math
class function_StyblinskiTang():
def __init__(self, size):
self.size = size
self.MIN_VAL = -5
self.MAX_VAL = 4
self.SCORE_MIN = -float('inf')
self.SCORE_MAX = 0

def init(self):
pass

def eval(self, arr):
n = sum([x ** 4 - 16*(x**2) + 5*x for x in np_arr])
return -n/2
``````

XinSheYang function

• One-dimensional graph

• 2D graph

• Program code
``````import math
class function_XinSheYang():
def __init__(self, size):
self.size = size
self.MIN_VAL = -2*math.pi
self.MAX_VAL = math.pi
self.SCORE_MIN = -float('inf')
self.SCORE_MAX = 0

def init(self):
pass

def eval(self, arr):
sum1 = sum([abs(x) for x in np_arr])
sum2 = sum([math.sin(x**2) for x in np_arr])
n = sum1 * math.exp(-sum2)
return -n
``````