# A Complexity Analysis of Evolutionary Algorithms

**URL:** <https://discourse.peacefulscience.org/t/a-complexity-analysis-of-evolutionary-algorithms/2637>\
**Category:** Side Conversation\
**Tags:** Science\
**Created:** [November 7, 2018, 12:28am UTC](https://discourse.peacefulscience.org/t/a-complexity-analysis-of-evolutionary-algorithms/2637 "2018-11-07T00:28:24Z")\
**Posts on this page:** 11\
**Page:** 2

<div class="post-metadata">

**Author:** ![swamidass](https://sea2.discourse-cdn.com/flex016/user_avatar/discourse.peacefulscience.org/swamidass/32/3_2.png) [@swamidass](https://discourse.peacefulscience.org/u/swamidass)\
**Post date:** [November 26, 2018, 4:47pm UTC](https://discourse.peacefulscience.org/t/a-complexity-analysis-of-evolutionary-algorithms/2637/22 "2018-11-26T16:47:20Z")

</div>

Dan, you might have to explain more about the problem, and produce some graphs of the scaling, right?

---

<div class="post-metadata">

**Author:** ![Dan\_Eastwood](https://sea2.discourse-cdn.com/flex016/user_avatar/discourse.peacefulscience.org/dan_eastwood/32/2368_2.png) [@Dan\_Eastwood](https://discourse.peacefulscience.org/u/Dan_Eastwood)\
**Post date:** [November 26, 2018, 4:57pm UTC](https://discourse.peacefulscience.org/t/a-complexity-analysis-of-evolutionary-algorithms/2637/23 "2018-11-26T16:57:42Z")

</div>

> [@swamidass](#):
>
> you might have to explain more about the problem, and produce some graphs of the scaling

Yes and yes. This is a learning process for me, and I haven’t had much time to devote to it. I have a long list of things I want to try, but first I need to wrestle with Python until I learn to make it do what I want. Maybe Santa will bring me a Python for Dummies book? 😉

---

<div class="post-metadata">

**Author:** ![AllenWitmerMiller](https://sea2.discourse-cdn.com/flex016/user_avatar/discourse.peacefulscience.org/allenwitmermiller/32/2519_2.png) [@AllenWitmerMiller](https://discourse.peacefulscience.org/u/AllenWitmerMiller)\
**Post date:** [November 26, 2018, 5:05pm UTC](https://discourse.peacefulscience.org/t/a-complexity-analysis-of-evolutionary-algorithms/2637/24 "2018-11-26T17:05:24Z")

</div>

> [@Dan\_Eastwood](#):
>
> Yes and yes. This is a learning process for me, and I haven’t had much time to devote to it.

As I have mentioned previously, Genetic Algorithms played an important role in helping to re-educate and train my “intuitions” concerning the validity of evolutionary processes to mold populations. I’ve often pondered how to go about bringing those GA benefits to the average non-scientist.

One of impediments is that both the GA (Genetic Algorithms) and EA (Evolutonary Algorithms) terms tend to lead the average person to assume that these are algorithms which are confined to genetics or evolutionary biology. (Many even assume that EAs are “biased simulations” of life on earth meant to convince people that the Theory of Evolution is true.) Most people fail to grasp that GAs/EAs work because they depend on mathematical realities which can be applied in practical ways in countless fields, from engineering to biochemistry and even to architecture and music. So I’ve sometimes wished that there was an appropriate alternative term, yet I haven’t come up with an alternative so far.

Of course, at some point we just have to accept the fact that it can be very difficult to grasp intuitively such complex scientific concepts without actually making the concerted effort to learn the fundamentals of science.

---

<div class="post-metadata">

**Author:** ![Dan\_Eastwood](https://sea2.discourse-cdn.com/flex016/user_avatar/discourse.peacefulscience.org/dan_eastwood/32/2368_2.png) [@Dan\_Eastwood](https://discourse.peacefulscience.org/u/Dan_Eastwood)\
**Post date:** [November 26, 2018, 5:19pm UTC](https://discourse.peacefulscience.org/t/a-complexity-analysis-of-evolutionary-algorithms/2637/25 "2018-11-26T17:19:34Z")

</div>

> [@AllenWitmerMiller](#):
>
> I’ve often pondered how to go about bringing those GA benefits to the average non-scientist.

Once I scanned the comments at [BoxCar2D.com](http://BoxCar2D.com), and there was a person objecting to evolution, saying that GA’s can’t work, despite the demonstration that was literally right in front of him. :-/

One thing I’d really like to look into is the **unfitness function** , which decides which members of the population to remove. How this is done has a huge effect on how the solution converges. There is probably some literature on this subject too - I should look.

---

<div class="post-metadata">

**Author:** ![AllenWitmerMiller](https://sea2.discourse-cdn.com/flex016/user_avatar/discourse.peacefulscience.org/allenwitmermiller/32/2519_2.png) [@AllenWitmerMiller](https://discourse.peacefulscience.org/u/AllenWitmerMiller)\
**Post date:** [November 26, 2018, 5:44pm UTC](https://discourse.peacefulscience.org/t/a-complexity-analysis-of-evolutionary-algorithms/2637/26 "2018-11-26T17:44:23Z")

</div>

> [@Dan\_Eastwood](#):
>
> Once I scanned the comments at [BoxCar2D.com](http://BoxCar2D.com), and there was a person objecting to evolution, saying that GA’s can’t work, despite the demonstration that was literally right in front of him. :-/

I noticed that too!

Indeed, though I have used the BoxCar2D illustration many times, I can’t say that anyone ever replied “Oh, that really clears things up! Now I understand what you are saying.” Hopefully it may have helped some silent third-party bystanders.

Years ago I used to use Conway’s Game of Life with my students. Of course, among mathematicians that is a classic paper.

> [@Dan\_Eastwood](#):
>
> One thing I’d really like to look into is the **unfitness function** , which decides which members of the population to remove. How this is done has a huge effect on how the solution converges.

Great idea!

---

<div class="post-metadata">

**Author:** ![AllenWitmerMiller](https://sea2.discourse-cdn.com/flex016/user_avatar/discourse.peacefulscience.org/allenwitmermiller/32/2519_2.png) [@AllenWitmerMiller](https://discourse.peacefulscience.org/u/AllenWitmerMiller)\
**Post date:** [November 26, 2018, 5:46pm UTC](https://discourse.peacefulscience.org/t/a-complexity-analysis-of-evolutionary-algorithms/2637/27 "2018-11-26T17:46:28Z")

</div>

By the way, I don’t think I’ve ever seen the ICR (Institute for Creation Research) or AIG (Answers in Genesis) websites deal with Evolutionary Algorithms. Does anyone know if Hugh Ross and Reasons to Believe have written on EAs?

---

<div class="post-metadata">

**Author:** ![Dan\_Eastwood](https://sea2.discourse-cdn.com/flex016/user_avatar/discourse.peacefulscience.org/dan_eastwood/32/2368_2.png) [@Dan\_Eastwood](https://discourse.peacefulscience.org/u/Dan_Eastwood)\
**Post date:** [November 26, 2018, 6:00pm UTC](https://discourse.peacefulscience.org/t/a-complexity-analysis-of-evolutionary-algorithms/2637/28 "2018-11-26T18:00:49Z")

</div>

> [@AllenWitmerMiller](#):
>
> By the way, I don’t think I’ve ever seen [… any of those sources …] websites deal with Evolutionary Algorithms.

If they have, then it’s likely to be in connection with Dawkins’ WEASEL program, which had been much argued over in ID circles. I have an example of that too, but I have not had a chance to tinker with it yet (it’s not much to look at yet).

---

<div class="post-metadata">

**Author:** ![Dan\_Eastwood](https://sea2.discourse-cdn.com/flex016/user_avatar/discourse.peacefulscience.org/dan_eastwood/32/2368_2.png) [@Dan\_Eastwood](https://discourse.peacefulscience.org/u/Dan_Eastwood)\
**Post date:** [December 5, 2018, 11:14pm UTC](https://discourse.peacefulscience.org/t/a-complexity-analysis-of-evolutionary-algorithms/2637/29 "2018-12-05T23:14:02Z")

</div>

Interesting, and a quick read. The article includes some references I want to follow up on.

> **[Mathematical Simplicity May Drive Evolution’s Speed | Quanta Magazine](https://www.quantamagazine.org/computer-science-and-biology-explore-algorithmic-evolution-20181129/?fbclid=IwAR1t1gzrANXScYBm1jiw8W01MpYEXIP6c1vqZz256s8zFqgqRV__IyK1P-w)**
>
> Some researchers are using a complexity framework thought to be purely theoretical to understand evolutionary dynamics in biological and computational systems.

---

<div class="post-metadata">

**Author:** ![Mung](https://avatars.discourse-cdn.com/v4/letter/m/a5b964/32.png) [@Mung](https://discourse.peacefulscience.org/u/Mung)\
**Post date:** [December 6, 2018, 4:07pm UTC](https://discourse.peacefulscience.org/t/a-complexity-analysis-of-evolutionary-algorithms/2637/30 "2018-12-06T16:07:43Z")

</div>

> [@Dan\_Eastwood](#):
>
> Genetic Algorithms are efficient at solving complex problems.

Not much use for them as problem solving algorithms if they aren’t any good at it. 😉

It’s amazing to me though that in some online venues people will go so far as to deny that genetic algorithms are in fact problem solving algorithms.

---

<div class="post-metadata">

**Author:** ![Dan\_Eastwood](https://sea2.discourse-cdn.com/flex016/user_avatar/discourse.peacefulscience.org/dan_eastwood/32/2368_2.png) [@Dan\_Eastwood](https://discourse.peacefulscience.org/u/Dan_Eastwood)\
**Post date:** [December 6, 2018, 10:00pm UTC](https://discourse.peacefulscience.org/t/a-complexity-analysis-of-evolutionary-algorithms/2637/31 "2018-12-06T22:00:13Z")

</div>

I should have been careful to say “certain types” of problems. We could find example where other methods are more efficient.

There is speculation that [non-random methods for optimal solutions exist](https://www.quantamagazine.org/a-short-guide-to-hard-problems-20180716/) for any problem (difficult to prove). I think GA’s function well as general purpose problem solvers needing little or no specialization.

---

<div class="post-metadata">

**Author:** ![Dan\_Eastwood](https://sea2.discourse-cdn.com/flex016/user_avatar/discourse.peacefulscience.org/dan_eastwood/32/2368_2.png) [@Dan\_Eastwood](https://discourse.peacefulscience.org/u/Dan_Eastwood)\
**Post date:** [December 20, 2018, 7:23pm UTC](https://discourse.peacefulscience.org/t/a-complexity-analysis-of-evolutionary-algorithms/2637/32 "2018-12-20T19:23:46Z")

</div>

Stashing this here in case it might be useful:

> **[Amoeba finds approximate solutions to NP-hard problem in linear time](https://phys.org/news/2018-12-amoeba-approximate-solutions-np-hard-problem.html)**
>
> Researchers have demonstrated that an amoeba—a single-celled organism consisting mostly of gelatinous protoplasm—has unique computing abilities that may one day offer a competitive alternative to the methods used by conventional computers.

[Previous page](https://discourse.peacefulscience.org/t/a-complexity-analysis-of-evolutionary-algorithms/2637.md?page=1)