<- Back to Tasks

dev 3 infinite island migration loops (genes living forever.) Migration that defeats the purpose of migration.

Migration occurs on the x'th generation of the source island but migrates in to a neighboring island regardless of the generation number the destination island is on. Since islands are evolving independently and can be on any generation number at any time in relationship to each other it's possible for genes to land on an island at an earlier generation and then migrate again to another and another (even with very low migration settings) etc. causing an indefinite migration loop (genes that outlive the evo restarts!) as I've shown below in some screenshots. This is potentially a huge problem for diversity and curve fitting. There are some quick dirty ways to fix this island migration loop but that would ignore the other problems outlined bellow.


What is the purpose of the island migration system? Each island is supposed to be given some "time" (generations) to come up with its own individual solution and then these solutions should be mixed together but if the migrant lands on an island that is at a low generation then the landed island didn't have time to come up with a solution yet so defeats the purpose of the island/migration system. Landing on an island at too high of a generation # can be inefficient too because then the solutions don't have enough time left to mix together before the evo restart which again starts to defeat the purpose. We may as well have one big pool instead of islands if you aren't going to respect this process.

Basic island/migration GA experiments are based on a system of islands that all progress through evolution at the same time (in the context of generations or real time) retaining island individuality for a certain controlled number of generations. It is nice for CPU efficiency that you made the islands capable of running separate generation number progression avoiding any "island downtime" by restarting a single island when it's done and  allowing other islands to continue through their higher generations separately BUT migrations across islands (based on generation numbers) becomes not so simple. The migrants are also jumping back and forth through generations, essentially "time traveling randomly back and forth" breaking the individuality of their neighboring islands at uncontrolled unwanted  generation numbers.

Should the immigrant wait in a temporary queue for the target island to be completed the same generation number? That way if for example we have set 20 max generation and migration is set to every 14th generation, we can know that one gene migration lands on the neighboring island on start of generatio#15 and therefore could not migrate again and also could not live longer than the 20 generations max we set. Yes I think this would be best way to get migration functioning as intended.


Attachments
  • Votes +1
  • Project StrategyQuant X
  • Type Bug
  • Status Fixed
  • Priority Normal

History

b
#1

bentra

18.03.2021 03:10

Task created

b
#2

bentra

18.03.2021 03:17
Voted for this task.
MF
#3

Mark Fric

18.03.2021 08:33

Status changed from New to Refused

why should we necessarily complicate it like this?


Islands run independently of each other, they have different evolution speeds because of random starting points. I don't see anything wrong accepting migrants as they do it now, controlling it accordign to your descrioption would not bring any new quality to the process.

b
#4

bentra

18.03.2021 12:36

Attachment Screenshot 209.png added

Screenshot 209.png
Screenshot 209.png
(676.69 KiB)
They do not start at random starting points in the context of generations. They always start at generation number one. The higher the generation the more likely they will be over-fitted, that's why we limit the generations.... The FITNESS starts randomly but that isn't as concerning in the context of over-fitting.

The problem is a single gene looping through many migrations/islands even when migration is set at 1% and only one migration is scheduled per island evolution, my suggestion is just a suggestion, there are many other ways to resolve it.  You can see in the screenshot this gene has appeared in 5 different islands!
b
#5

bentra

18.03.2021 14:04

Attachment Screenshot 218.png added

Attachment Screenshot 217.png added

Attachment Screenshot 216.png added

Attachment Screenshot 215.png added

Attachment Screenshot 214.png added

Attachment Screenshot 213.png added

Attachment Screenshot 212.png added

Screenshot 218.png
Screenshot 218.png
(213.84 KiB)
Screenshot 217.png
Screenshot 217.png
(803.31 KiB)
Screenshot 214.png
Screenshot 214.png
(809.66 KiB)
Screenshot 212.png
Screenshot 212.png
(809.26 KiB)
Screenshot 215.png
Screenshot 215.png
(779.63 KiB)
Screenshot 216.png
Screenshot 216.png
(812.11 KiB)
Screenshot 213.png
Screenshot 213.png
(812.24 KiB)
With migration ramped up a bit I was easily able to reproduce a migration loop through every single island and so possibly infinite (like I was warning about originally) in 17 minutes. 


b
#6

bentra

18.03.2021 14:29

Subject changed from dev 3 potential island migration loop and or genes outliving the maximum number of generations to dev 3 infinite island migration loop possible and genes living forever

b
#7

bentra

18.03.2021 20:10
It is nice for CPU efficiency that you made the islands capable of running on their own at there own pace but migrations becomes not so simple. The migrants are also jumping back and forth through generations, "time traveling randomly." The jumping back in generations opens the door to for genes to stay alive forever and to migrate infinitely or at least for a very long time much longer than expected. Jumping forward in generations can also be bad, it cuts short the life of the migrant not allowing it to do it's thing on the new island. My idea is still the best one I can think of simply disallowing such "time travel" while at the same time guaranteeing that no genes live longer than max generations. 


With my suggestion the migration would have the exact same effect as  other gen algos where all islands are advancing together.  I was surprised that it was not originally implemented this way. Each island is supposed to come up with its own solution and then these solutions should be mixed together but if the migrant lands on an island at a low generation then the landed island didn't have time to come up with a solution yet so defeats the purpose of migration.

MF
#8

Mark Fric

26.03.2021 12:22

Status changed from Refused to Fixed

ok, you managed to persuade me to solve this.


I still think it is an edge case, but it is not too much work to fix it.


What I did -  migrated strategies will be first accepted by the island only if its generation reaches the migration generation. 

This should give island enough time to evolve.

Votes: +1

Drop files to upload

or

choose files

Max size: 5MB

Not allowed: exe, msi, application, reg, php, js, htaccess, htpasswd, gitignore

...
Wait please