Genetic searchers for spaceships -- viable?
Posted: April 15th, 2015, 5:05 pm
High-period spaceships remain difficult to search for with current techniques due to the great computational demands. But a great deal of advancement in terms of computation comes not from hardware improvement, but developing better algorithms. Personally, I don't understand the algorithms used in existing software because I don't understand programming or scripting in general, but as far as I'm aware, there are no genetic searchers for spaceships or oscillators.
Here's a naive example of what I mean:
The naive algorithm would construct a series of soups of specified size, involving whichever fixed cell states are specified by the user (known partials, for example). These would be evolved by the desired period of the ship to result in a product, and the similarity between the soup and its product would be scored based on the number of matching ON cells and, to a lesser extent, OFF cells. Perhaps the "better" half of the soups would then be selected, and some combination of mutations and combinations would be performed to acquire a new series of soups based on the survivors. This new series would be evolved by the desired period of the ship, and so on. At each iteration, the top scoring soup would be printed to an output file, and when a soup that exactly matches its own product is found, it will be printed as well, and the search stopped.
Would a search program along these lines be feasible at all? It couldn't hurt to put together a python script along these lines and see how long it takes to find a c/3 ship or somesuch.
Here's a naive example of what I mean:
The naive algorithm would construct a series of soups of specified size, involving whichever fixed cell states are specified by the user (known partials, for example). These would be evolved by the desired period of the ship to result in a product, and the similarity between the soup and its product would be scored based on the number of matching ON cells and, to a lesser extent, OFF cells. Perhaps the "better" half of the soups would then be selected, and some combination of mutations and combinations would be performed to acquire a new series of soups based on the survivors. This new series would be evolved by the desired period of the ship, and so on. At each iteration, the top scoring soup would be printed to an output file, and when a soup that exactly matches its own product is found, it will be printed as well, and the search stopped.
Would a search program along these lines be feasible at all? It couldn't hurt to put together a python script along these lines and see how long it takes to find a c/3 ship or somesuch.