HOME | DD

Description
So in this semester I have Artificial Intelligance discipline at uni. And we have few home works there.

I think that it may be interesting for some of you people so posted result of first home work.
It is about genetic algorithms.

Info on genetic algorithms
[link] - read here for better info. In short GA is one of not many ways of optimizing/searching something in field that is hard to formalize. For example if you know the function in which you look for minimal value you could use mathematics to try and solve that task. But for that you should have a very good knowledge in math and task should have appropriate mathematical representation. But in realty many tasks and problems often don’t have correct mathematical representation or representation is too hard for math to solve. So here GA helps. Thing is that principles in it allow it to find solutions in any sphere and task. Though it comes at a price of time and uncertainty. For example you can’t be 100% shore when to stop the algorithm.
Idea is simple. You usually can represent solutions as some number sequence. Then you can create criteria to judge solutions based on how good they are. Using those things you make an algorithm that creates populations of random solutions and starts an evolutionary process in which solutions compete/reproduce/mutate trying to be judged better.

Aims
So I changed the task a little so that result would be more representable.

This program receives a graph and then tries to find best mapping of graph nodes to 25x25 grid so that number of collision among edges of graph would be minimal. In some way you may say that it should untangle the graph

Explanations on interface

You can input a graph matrix in to the GraphString box and hit restart. Then algorithm will rebuild inner matrix and start looking solutions for it. String represents squired oriented incidence matrix of 0/1. Each number says if route from x node to y node exists. By default a graph of 25 nodes with that are connected in a circle is imputed.
So that means that each creature is represented by array of mapping coordinates for each node in the graph. For 3 noded triangle graphs matrix will be:
010
001
100
and creature will be:
[[0,0],[25,25],[0,25]]

You can choose one of items in generation list to see actual graph. By default after each calculation it chooses best creature to show. Sometimes you will need to click few times before it selects a creature. Thing is that algorithm runs in parallel to interface and list does not catch some of the clicks

Then there are options on parameters of algorithm:

Population size: how many creatures are created.

% of survivors: - sets % of population that is chosen are representatives that fit for reproduction. Say that with population of 100 and survivors of 50% it will chose 50 creatures and will create 50 more children from them. Children I made by choosing random pair of creatures and then creating new one with characteristics randomly taken from parents.

% of mutations: % of creatures that will be chosen for mutation.

% of effect: % of characteristics of creatures that will be randomly changed in mutation process.

Seems like that’s all. Usually somewhere in 200 generations it untangles the initial graph. Though it depends on luck.

Edit: Added start/stop button and fixed one bug.

Description
So in this semester I have Artificial Intelligance discipline at uni. And we have few home works there.

I think that it may be interesting for some of you people so posted result of first home work.
It is about genetic algorithms.

Info on genetic algorithms
[link] - read here for better info. In short GA is one of not many ways of optimizing/searching something in field that is hard to formalize. For example if you know the function in which you look for minimal value you could use mathematics to try and solve that task. But for that you should have a very good knowledge in math and task should have appropriate mathematical representation. But in realty many tasks and problems often don’t have correct mathematical representation or representation is too hard for math to solve. So here GA helps. Thing is that principles in it allow it to find solutions in any sphere and task. Though it comes at a price of time and uncertainty. For example you can’t be 100% shore when to stop the algorithm.
Idea is simple. You usually can represent solutions as some number sequence. Then you can create criteria to judge solutions based on how good they are. Using those things you make an algorithm that creates populations of random solutions and starts an evolutionary process in which solutions compete/reproduce/mutate trying to be judged better.

Aims
So I changed the task a little so that result would be more representable.

This program receives a graph and then tries to find best mapping of graph nodes to 25x25 grid so that number of collision among edges of graph would be minimal. In some way you may say that it should untangle the graph

Explanations on interface

You can input a graph matrix in to the GraphString box and hit restart. Then algorithm will rebuild inner matrix and start looking solutions for it. String represents squired oriented incidence matrix of 0/1. Each number says if route from x node to y node exists. By default a graph of 25 nodes with that are connected in a circle is imputed.
So that means that each creature is represented by array of mapping coordinates for each node in the graph. For 3 noded triangle graphs matrix will be:
010
001
100
and creature will be:
[[0,0],[25,25],[0,25]]

You can choose one of items in generation list to see actual graph. By default after each calculation it chooses best creature to show. Sometimes you will need to click few times before it selects a creature. Thing is that algorithm runs in parallel to interface and list does not catch some of the clicks

Then there are options on parameters of algorithm:

Population size: how many creatures are created.

% of survivors: - sets % of population that is chosen are representatives that fit for reproduction. Say that with population of 100 and survivors of 50% it will chose 50 creatures and will create 50 more children from them. Children I made by choosing random pair of creatures and then creating new one with characteristics randomly taken from parents.

% of mutations: % of creatures that will be chosen for mutation.

% of effect: % of characteristics of creatures that will be randomly changed in mutation process.

Seems like that’s all. Usually somewhere in 200 generations it untangles the initial graph. Though it depends on luck.

Edit: Added start/stop button and fixed one bug.