Create and Visualize Polygons with Genetic Algorithm | Python

Genetic Algorithm Polygon Generation.

Who would have thought watching your code generate polygons, generation after generation, would be that much fun and enjoyable.

I have come up to share with you guys my implementation of a python program that uses Genetic Algorithm to generate a perfect polygon. A closed polygon that has no intersections between its edges.

If your not familiar with GA, here’s how it goes:

Genetic Algorithm: is a search optimization technique for finding the best or optimal solution over a vast possible search space (solutions) without putting hard constraints to guide it to the best solution. The guiding mechanism of GA are the methods applied to initial input.

GA consists of 5 components:

1. Initial Population: input given to the algorithm.
2. Fitness Calculation: an objective function that specifies how close a solution is to the desired solution.
3. Parent Selection: selection of some solutions based upon some criteria for reproducing new offspring solutions.
4. Crossover: a mechanism applied to the parent solution for the formation of offspring chromosome.
5. Mutation: modification of an individual solution’s chromosome based upon chance or probability.

So, methods 2 to 5 are applied iteratively for a number of generations to obtain the optimal solution. New good solutions generated in every generation replaces the old poor solutions. In this way, the population is modified with every generation containing the best solutions.

Termination Criteria: the algorithm either stops when the number of generations ends or some success criteria is achieved.

Polygon Generation

The implementation of the program can be found in my Github repo. The flow chart of the program is as follows:

Polygon Generation Program Flowchart

The program is explained in the repo, but here’s a quick overview:

main: initializes the necessary variables required for the algorithm such as population size, domain points, crossover & mutation probabilities etc. Domain points are the 2d points that act as vertices for polygons. Hence, each individual solution or chromosome size in the population equals the size of domain points.

Individual Solution Structure:

chromosome: list of random 0s and 1s    -> [1,1,1]
polygon_sequence: list of 2d vertices  -> [(x1,y1),(x2,y2),(x3,y3)] 
num_intersection: num of intersections in this polygon  -> 0 
value: differnce betweem sum 1s of chromosome and num_intersection  -> 3

A chromosome that has a gene with value 0, does not include its corresponding domain point in the creation of a polygon. For example, the following individual solution will create a polygon with three vertices excluding the point: (x2,y2).

chromosome: [1,0,1,1]
polygon_sequence: [(x1,y1),(x2,y2),(x3,y3),(x4,y4)]

runGA: generates the initial population and iterates over the methods to obtain the optimal solution.

Fitness Calculation: fitness of a solution is calculated by two functions:

1. create_polygon: The polygon is created (if possible) from the polygon sequence edge by edge. The vertices are connected in sequential order to make edges.
2. check_intersection: Each newly created edge is check for intersections with the previous edges of the polygon. If intersection occurs, num_intersection is incremented.

Success Criteria: a polygon made of all the domain points having no intersection among its edges.

Visualizing the Polygons

Matplotlib is used for visualizing the polygons. Here is the glimpse of a sample output of the program:

Polygons after 4 generations

A polygon of 6 vertices is created after 3 generations in the 4th generation without having any intersections.

As mentioned before, the generation of the optimal solution is dependent on the number of generations, size of polygon, and the polygon creation function. The function that I have implemented creates polygon sequentially from its polygon_sequence. There may arise a problem that the sequential connection if the vertices may, at times, generate a polygon that has intersections and, thus, cause the program to iterate over to next generation. This is so to avoid a complex polygon creation function.

You may come up with another polygon creation function that doesn’t create polygon sequentially. And, it may also increase the chances for early generation of polygon of larger size.

Wrap-up

Thank you for reading till the end! I hope this blog helps you in your learning. Hit the like, star the repo, and share with others if you found it beneficial.

Interested in reading more of my work:

JavaScript Function Declaration VS Function Expression

https://medium.com/@csprongineer/getting-started-with-react-native-a11f84c493fa

Getting Started With React Native