Suppose we have such a biological group , Each of their gene fragments is a triangle （ That is, it only contains three points and color information ）, The trait that each individual shows is the superposition of several triangles . Suppose we have a picture that can be used as the most adaptive trait of this biological population , That is, the more you look like this picture, the more you can adapt to the environment , The less like this picture, the easier it is to be eliminated .
Of course, as a normal biological group , He should also have normal reproduction to produce new individuals . In the process of producing new individuals, genes from father and mother will cross exchange and mutate , Mutations can also add gene fragments 、 Reduce the sequence exchange of gene fragments and gene fragments at different positions .
But a population cannot reproduce indefinitely , We assume that environmental resources can only accommodate a limited number of biological populations , So after we produce enough offspring, we have to put them into the ethnic group to compete and eliminate them . thus , Through constant elimination , This group will be more and more like the picture we give . This is the basic idea of the algorithm .
Let's take a look at the implementation process , For the convenience of explanation , We will combine python Create a pseudo code like function to explain , Can't run directly , The specific runnable code can be directly downloaded by referring to the complete code encapsulated by the last class
We use imageio Medium imread Open the picture , Here, for the convenience of subsequent use, we establish OpenImg function , Return to the open picture img（ The format is array）, The format of the picture （ It is convenient to save the pictures in the later period ）, Size of picture ：row and col（ Prepare for later drawing ）.
from imageio import imread
def OpenImg(imgPath):
img = imread(imgPath)
row, col = img.shape[0], img.shape[1]
return img, imgPath.split(".")[-1], row, col
We assume that the maximum number of organisms in a population is max_group, use groups To represent the ethnic group ,g It is the biological individual in the group , Use random numbers to randomly generate individuals .
from random import choice
for i in range(max_group):
g = []
for j in range(features):
tmp = [[choice(np.linspace(0, row, features)), choice(np.linspace(0, col, features))] for x in range(3)]
tmp.append("#" + ''.join(choice('0123456789ABCDEF') for x in range(6)))
g.append(tmp.copy())
groups.append(g.copy())
We use PIL drawing , First we create a blank canvas , Then the individual characteristics （ triangle ） Draw on the picture .
from PIL import Image, ImageDraw
def to_image(g):
array = np.ndarray((img.shape[0], img.shape[1], img.shape[2]), np.uint8)
array[:, :, 0] = 255
array[:, :, 1] = 255
array[:, :, 2] = 255
newIm1 = Image.fromarray(array)
draw = ImageDraw.Draw(newIm1)
for d in g:
draw.polygon((d[0][0], d[0][1], d[1][0], d[1][1], d[2][0], d[2][1]), d[3])
return newIm1
Use structural_similarity Compare the similarity of two pictures , Both pictures should be array type
from skimage.metrics import structural_similarity
def getSimilar(g) -> float:
newIm1 = to_image(g)
ssim = structural_similarity(np.array(img), np.array(newIm1), multichannel=True)
return ssim
Call our previously established to_image Function first converts an individual into a picture , Then save the picture .
def draw_image(g, cur, imgtype):
image1 = to_image(g)
image1.save(os.path.join(str(cur) + "." + imgtype))
Considering the increase and decrease of gene fragments in the later stage , So it should be divided into two steps , One is to cross exchange the overlapped positions , And cross swap the extra tails , We follow the random rate random_rate And coincident position length min_locate To determine the number of bits exchanged . And then we use sample Select several positions to exchange . After the exchange, the tail shall be exchanged
random_rate = random()
def exchange(father, mother)->[]:
# In exchange for
# Randomly generate the number of interchanges
min_locate = min(len(father), len(mother))
n = randint(0, int(random_rate * min_locate))
# Randomly select multiple locations
selected = sample(range(0, min_locate), n)
# Exchange internal
for s in selected:
father[s], mother[s] = mother[s], father[s]
# Swap tails
locat = randint(0, min_locate)
fhead = father[:locat].copy()
mhead = mother[:locat].copy()
ftail = father[locat:].copy()
mtail = mother[locat:].copy()
# print(fhead, ftail, mhead, mtail)
fhead.extend(mtail)
father = fhead
mhead.extend(ftail)
mother = mhead
return [father, mother]
The principle and purpose of random selection are similar to the above , Here we regard the information of regenerating a certain gene segment as gene mutation .
random_rate = random()
def mutation(gen):
# mutation
# Number of randomly generated variants
n = randint(0, int(random_rate * len(gen)))
selected = sample(range(0, len(gen)), n)
for s in selected:
tmp = [[choice(np.linspace(0, row, 100)), choice(np.linspace(0, col, 100))] for x in range(3)]
tmp.append("#" + ''.join(choice('0123456789ABCDEF') for x in range(6)))
gen[s] = tmp
return gen
Random selection of gene fragments in an individual's genome for position exchange .
def move(gen):
# translocation
exchage = randint(0, max_group // 2)
for e in range(exchage):
sec1 = randint(0, len(gen) - 1)
sec2 = randint(0, len(gen) - 1)
gen[sec1], gen[sec2] = gen[sec2], gen[sec1]
return gen
Add randomly generated gene fragments directly behind the individual genome .
features = 100
def add(gen):
# increase
n = randint(0, int(features * 0.3))
for s in range(n):
tmp = [[choice(np.linspace(0, row,features)),choice(np.linspace(0, col, features))] for x in range(3)]
tmp.append("#" + ''.join(choice('0123456789ABCDEF') for x in range(6)))
gen.append(tmp)
return gen
Randomly reduce the number of individual gene fragments
def cut(gen):
# Reduce
n = randint(0, int(self.random_rate * len(gen)))
selected = sample(range(0, len(gen)), n)
g = []
for gp in range(len(gen)):
if gp not in selected:
g.append(gen[gp])
return g
To invoke the above mutation 、 translocation 、 Increase and decrease production 4 A gene fragment in one state
def variation(gen):
# variation
gen = mutation(gen.copy())
gen1 = move(gen.copy())
gen2 = add(gen1.copy())
gen3 = cut(gen2.copy())
return [gen, gen1, gen2, gen3]
The breeding process includes cross exchange and variation , Directly call the previously constructed function
def breeds(father, mother):
new1, new2 = exchange(father.copy(), mother.copy())
# variation
new3, new4, new5, new6 = variation(father.copy())
new7, new8, new9, new10 = variation(mother.copy())
return [new1, new2, new3, new4, new5, new6, new7, new8, new9, new10]
Establish the mapping relationship between the individual and its similarity with the target , And sort according to the similarity , Then remove the individuals with low similarity , Until the number of remaining individuals is max_group until . In this function, we also return the similarity of an optimal individual to facilitate monitoring .
def eliminated(groups):
group_dict = dict()
for gp in range(len(groups)):
group_dict[gp] = getSimilar(groups[gp])
group_dict = {
key: value for key, value in sorted(group_dict.items(), key=lambda item: item[1], reverse=True)}
g = []
for key in list(group_dict.keys())[:max_group]:
g.append(groups[key].copy())
groups = g.copy()
return groups, list(group_dict.values())[0]
The fitting process starts with several times of reproduction , In order to ensure the number of individuals per breeding, we stipulate that they should select at least half of the maximum number of individuals for breeding , The individuals after breeding are added to the population and eliminated together with the individuals in the previous population . Through this process, we will eliminate the individual with the greatest gap with the goal every time .
def fit():
for cur in range(epochs):
# Reproductive process
breed_n = randint(int(max_group // 2),max_group)
for i in range(breed_n):
f = randint(0, max_group - 1)
m = randint(0, max_group - 1)
groups.extend(breeds(groups[f].copy(), groups[m].copy()))
# Eliminate
groups, acc = eliminated(groups.copy())
print("Epochs :", cur, " Acc:", acc)
if cur % 100 == 0:
draw_image(groups[0], cur)
if acc >= 0.95:
draw_image(groups[0], cur)
break
GitHub Download address （ recommend ）：
https://github.com/AiXing-w/Python-Intelligent-Optimization-Algorithms
CSDN Download address ：
https://download.csdn.net/download/DuLNode/81708589
