Body: <p>I have been reading about the <a href="https://en.wikipedia.org/wiki/Holland%27s_schema_theorem" rel="nofollow noreferrer"><strong>Schema Theorem</strong></a> - one of the first theorems from the field of evolutionary computing and genetic algorithms, largely responsible for justifying the use of genetic algorithms to solve optimization problems when the derivative of the objective function is either unknown or not clearly defined.</p>
  <p>Genetic algorithms can be used in many different types of optimization problems, such as finding the roots of a polynomial. For example, we could use the genetic algorithm to find the roots (the zeros) of the following polynomial (this polynomial will be referred to as the objective function, i.e. the objective of the optimization/root finding):</p>
  <p><span class="math-container">$$f(x, y) = x \sin(4x) + 1.1 y \sin(2y)$$</span></p>
  <p>Essentially, the genetic algorithm would start by taking random values of <span class="math-container">$x$</span> and <span class="math-container">$y$</span> and record the corresponding value of <span class="math-container">$f(x,y)$</span> for each random combination of <span class="math-container">$x$</span> and <span class="math-container">$y$</span>: the value of <span class="math-container">$f(x,y)$</span> for a given combination of <span class="math-container">$x$</span> and <span class="math-container">$y$</span> is called the &quot;fitness&quot;. The genetic algorithm works by taking many such random combinations of <span class="math-container">$x$</span> and <span class="math-container">$y$</span> and recording which combinations produce lower fitness values (i.e. which coordinates of <span class="math-container">$x$</span> and <span class="math-container">$y$</span> correspond to low elevation regions on the <span class="math-container">$f(x,y)$</span> surface). The genetic algorithm then combines (i.e. mutates) combinations of <span class="math-container">$x$</span> and <span class="math-container">$y$</span> that produced low fitness values, and re-evaluates <span class="math-container">$f(x,y)$</span> at these new mutated combinations of <span class="math-container">$x$</span> and <span class="math-container">$y$</span>. The genetic algorithm repeats this mutation process many times until it successive differences in <span class="math-container">$f(x,y)$</span> are negligible, or after a predefined number of iterations - this is very useful in problems where evaluating the derivative of the objective function can be extremely time-consuming or costly, or the derivative of the objective function is poorly defined (i.e. standard optimization algorithms like gradient descent and newton-raphson can not be performed).</p>
  <p>An interesting observation about the genetic algorithm is that it <strong>does not promise or guarantee convergence to the true minimum point of the objective function</strong> during the optimization process. But what the genetic algorithm does guarantee is that <strong>the overall fitness of the objective function is guaranteed to improve as the number of iterations increases</strong>. This idea is expressed in one of the original and fundamental theorems of genetic algorithms, called the <a href="https://en.wikipedia.org/wiki/Holland%27s_schema_theorem" rel="nofollow noreferrer"><strong>Schema Theorem</strong></a>.</p>
  <p>Apparently, this theorem states that &quot;schemas&quot; (e.g. combinations of <span class="math-container">$x$</span> and <span class="math-container">$y$</span>) that produce better fitness values are more likely to survive after mutation - i.e. the expected number of &quot;schemas&quot; that produce better fitness values are likely to increase as the number of iterations increase.</p>
  <p><strong>Question:</strong> I have spent a long time trying to find a derivation of proof of the Schema Theorem - something which attempts to mathematically explain why the genetic algorithm is guaranteed to move towards the true optimum of the objection function as the number of iterations increase (rhetorical question: after all, why does the &quot;genetic algorithm&quot; not result in worse fitness results?). After all:</p>
  <p><span class="math-container">$$
  \mathrm{E}(m(H, t+1)) \geq \frac{m(H, t) f(H)}{a_{t}}[1-p]
  $$</span></p>
  <p><strong>Why does this inequality hold?</strong></p>
  <p>I am very curious to see if there is a mathematical proof that justifies one of the most important and earliest theorems in &quot;genetic algorithms&quot; and evolutionary computing; does the Schema Theorem have a mathematical proof?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-01-14T12:40:37.253Z
Comments.Text: Yeah, the schema theorem is rubbish. If you want to guarantee increasing fitness, just use elitism.
Comments.UserDisplayName: Ray
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-01-18T11:16:05.347Z
Comments.Text: I am not exactly following. The term "*theorem*" has a very specific and unambiguous meaning in mathematics; if there was not a proof, we would call it Schema *Axiom*, or Schema *Principle*, or Schema *Conjecture*, or - you get the idea. I could understand a question "*where can I find the proof of the Schema Theorem*", but if it *exists*? In any case, the obvious starting point for a proof would be Holland's [*Adaptation in Natural and Artificial Systems*](https://books.google.gr/books?id=5EgGaBkwvWcC&printsec=frontcover&redir_esc=y#v=onepage&q&f=false); have you consulted it?
Comments.UserDisplayName: desertnaut
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-01-18T11:31:07.190Z
Comments.Text: A quick Google search revealed [this slide deck](http://fuzzy.cs.ovgu.de/ci/ea/v06_schematheorem_en.pdf), which includes a section titled "*Proving the Schema Theorem*".
Comments.UserDisplayName: desertnaut
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-01-18T14:10:30.410Z
Comments.Text: I’m voting to close this question because asking if a mathematical *theorem* has a *proof* does not make any sense (the answer is trivially "*yes*"). If the question is about producing or *locating* a/the proof, please edit accordingly.
Comments.UserDisplayName: desertnaut
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-01-18T15:32:20.003Z
Comments.Text: @desertnaut Clearly, the OP doesn't know or clarify that what we usually call "theorem" in math has a proof and I think it's implicit that the OP isn't just looking for "yes, this theorem has a proof", but would also like someone to point him/her to the proof. In fact, the question starts with "I have spent a long time trying to find a **derivation of proof of the Schema Theorem**" and then asks "Why does this inequality hold?". So, my interpretation of this question is: "Why does the inequality hold, i.e. what's the intuition behind the proof of the schema theorem? Where can I find it?".
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-01-18T15:37:28.750Z
Comments.Text: The original post even contained more questions, i.e. "Why do genetic algorithms work?". I think the core of this post is "Why is this inequality true? So, what's the proof of this schema theorem or inequality? "
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-01-18T15:41:18.007Z
Comments.Text: @nbro Arguably, the question is adequately summarized in its last sentence: "*does the Schema Theorem have a mathematical proof?*", which arguably would also answer their previous question "*Why does this inequality hold?*". My simple argument is that, as is, this is an ill-posed question, trivially answered in the positive. I am afraid that the OP never answers "*What is the proof*", implicitly assuming a possibility that such a proof may not even exist, and **this** is not justified (the fact that I was able to locate such a proof after googling for 5' is another story, but not irrelevant).
Comments.UserDisplayName: desertnaut
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-01-18T15:43:49.003Z
Comments.Text: @nbro notice again: "*I am very curious to see **if** there is a mathematical proof [...]*" - again, completely unjustified. If they wanted to ask "*Where can I find the proof*", they could (and should) do so in just a couple of lines, without raising all that dust and implying that such a proof (of a *theorem*) may not even exist.
Comments.UserDisplayName: desertnaut
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-01-18T15:47:09.167Z
Comments.Text: @desertnaut In this worst case, someone that answers this question will just give a "yes" or "no" answer. In the best case, they will also explain the proof and provide and/or provide a link to the proof. I think the post is ambiguous in a way, but, as I said, to me the OP wants to understand that inequality, not only because that question is in bold but also because the original post contained the title "Why do GAs work?". I agree that this post contained multiple questions and it might not be clear which one is the main one.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-01-18T15:47:48.103Z
Comments.Text: For me, it's obvious that the main one is not "does the schema theorem have a proof?", but "what is the proof?". That's obvious because it's implied by the question "Why does this inequality hold?" The OP will eventually clarify what the main question is after having seen these comments.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-01-18T15:50:23.927Z
Comments.Text: @desertnaut In any case, I think this is one of the most fundamental questions that could have been asked here. So, voting to close this question for me is not the right thing to do, as the main question to me is obvious. There are examples of many other questions that should have been closed, if you want to vote to close them. For example, [this](https://ai.stackexchange.com/q/34184/2444).
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-01-18T15:56:59.357Z
Comments.Text: @nbro if the main question is obvious to you, then kindly **edit** the question to remove any ambiguities (as I have explicitly suggested in my close vote). I can't see how "*this is one of the most fundamental questions that could have been asked here*" - anyone understanding the meaning of the term "*theorem*" is aware that there *is* a proof, and it is findable, for anyone really interested.
Comments.UserDisplayName: desertnaut
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-01-18T16:00:35.657Z
Comments.Text: And bold in itself says nothing; the last sentence was also in bold, which I edited out myself.
Comments.UserDisplayName: desertnaut
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-01-18T16:04:06.977Z
Comments.Text: Let us [continue this discussion in chat](https://chat.stackexchange.com/rooms/133314/discussion-between-nbro-and-desertnaut).
Comments.UserDisplayName: nbro
Tags: <optimization><genetic-algorithms><proofs>
Title: Why does the schema theorem of genetic algorithms hold?
UserDisplayName: stats_noob
ThreadText: # Why does the schema theorem of genetic algorithms hold?
  
  (Asked by: username_0 on 2022-01-14)
  
  I have been reading about the [**Schema Theorem**](https://en.wikipedia.org/wiki/Holland%27s_schema_theorem) - one of the first theorems from the field of evolutionary computing and genetic algorithms, largely responsible for justifying the use of genetic algorithms to solve optimization problems when the derivative of the objective function is either unknown or not clearly defined.
  
  Genetic algorithms can be used in many different types of optimization problems, such as finding the roots of a polynomial. For example, we could use the genetic algorithm to find the roots (the zeros) of the following polynomial (this polynomial will be referred to as the objective function, i.e. the objective of the optimization/root finding):
  
  $$f(x, y) = x \sin(4x) + 1.1 y \sin(2y)$$
  
  Essentially, the genetic algorithm would start by taking random values of $x$ and $y$ and record the corresponding value of $f(x,y)$ for each random combination of $x$ and $y$: the value of $f(x,y)$ for a given combination of $x$ and $y$ is called the "fitness". The genetic algorithm works by taking many such random combinations of $x$ and $y$ and recording which combinations produce lower fitness values (i.e. which coordinates of $x$ and $y$ correspond to low elevation regions on the $f(x,y)$ surface). The genetic algorithm then combines (i.e. mutates) combinations of $x$ and $y$ that produced low fitness values, and re-evaluates $f(x,y)$ at these new mutated combinations of $x$ and $y$. The genetic algorithm repeats this mutation process many times until it successive differences in $f(x,y)$ are negligible, or after a predefined number of iterations - this is very useful in problems where evaluating the derivative of the objective function can be extremely time-consuming or costly, or the derivative of the objective function is poorly defined (i.e. standard optimization algorithms like gradient descent and newton-raphson can not be performed).
  
  An interesting observation about the genetic algorithm is that it **does not promise or guarantee convergence to the true minimum point of the objective function** during the optimization process. But what the genetic algorithm does guarantee is that **the overall fitness of the objective function is guaranteed to improve as the number of iterations increases**. This idea is expressed in one of the original and fundamental theorems of genetic algorithms, called the [**Schema Theorem**](https://en.wikipedia.org/wiki/Holland%27s_schema_theorem).
  
  Apparently, this theorem states that "schemas" (e.g. combinations of $x$ and $y$) that produce better fitness values are more likely to survive after mutation - i.e. the expected number of "schemas" that produce better fitness values are likely to increase as the number of iterations increase.
  
  **Question:** I have spent a long time trying to find a derivation of proof of the Schema Theorem - something which attempts to mathematically explain why the genetic algorithm is guaranteed to move towards the true optimum of the objection function as the number of iterations increase (rhetorical question: after all, why does the "genetic algorithm" not result in worse fitness results?). After all:
  
  $$
  \mathrm{E}(m(H, t+1)) \geq \frac{m(H, t) f(H)}{a\_{t}}[1-p]
  $$
  
  **Why does this inequality hold?**
  
  I am very curious to see if there is a mathematical proof that justifies one of the most important and earliest theorems in "genetic algorithms" and evolutionary computing; does the Schema Theorem have a mathematical proof?
  
  **Tags:** optimization, genetic-algorithms, proofs
  
  > **Comments:**
  > **username_1**: Yeah, the schema theorem is rubbish. If you want to guarantee increasing fitness, just use elitism.  
  > **username_2**: I am not exactly following. The term "*theorem*" has a very specific and unambiguous meaning in mathematics; if there was not a proof, we would call it Schema *Axiom*, or Schema *Principle*, or Schema *Conjecture*, or - you get the idea. I could understand a question "*where can I find the proof of the Schema Theorem*", but if it *exists*? In any case, the obvious starting point for a proof would be Holland's [*Adaptation in Natural and Artificial Systems*](https://books.google.gr/books?id=5EgGaBkwvWcC&printsec=frontcover&redir_esc=y#v=onepage&q&f=false); have you consulted it?  
  > **username_2**: A quick Google search revealed [this slide deck](http://fuzzy.cs.ovgu.de/ci/ea/v06_schematheorem_en.pdf), which includes a section titled "*Proving the Schema Theorem*".  
  > **username_2**: I’m voting to close this question because asking if a mathematical *theorem* has a *proof* does not make any sense (the answer is trivially "*yes*"). If the question is about producing or *locating* a/the proof, please edit accordingly.  
  > **username_3**: @username_2 Clearly, the OP doesn't know or clarify that what we usually call "theorem" in math has a proof and I think it's implicit that the OP isn't just looking for "yes, this theorem has a proof", but would also like someone to point him/her to the proof. In fact, the question starts with "I have spent a long time trying to find a **derivation of proof of the Schema Theorem**" and then asks "Why does this inequality hold?". So, my interpretation of this question is: "Why does the inequality hold, i.e. what's the intuition behind the proof of the schema theorem? Where can I find it?".  
  > **username_3**: The original post even contained more questions, i.e. "Why do genetic algorithms work?". I think the core of this post is "Why is this inequality true? So, what's the proof of this schema theorem or inequality? "  
  > **username_2**: @username_3 Arguably, the question is adequately summarized in its last sentence: "*does the Schema Theorem have a mathematical proof?*", which arguably would also answer their previous question "*Why does this inequality hold?*". My simple argument is that, as is, this is an ill-posed question, trivially answered in the positive. I am afraid that the OP never answers "*What is the proof*", implicitly assuming a possibility that such a proof may not even exist, and **this** is not justified (the fact that I was able to locate such a proof after googling for 5' is another story, but not irrelevant).  
  > **username_2**: @username_3 notice again: "*I am very curious to see **if** there is a mathematical proof [...]*" - again, completely unjustified. If they wanted to ask "*Where can I find the proof*", they could (and should) do so in just a couple of lines, without raising all that dust and implying that such a proof (of a *theorem*) may not even exist.  
  > **username_3**: @username_2 In this worst case, someone that answers this question will just give a "yes" or "no" answer. In the best case, they will also explain the proof and provide and/or provide a link to the proof. I think the post is ambiguous in a way, but, as I said, to me the OP wants to understand that inequality, not only because that question is in bold but also because the original post contained the title "Why do GAs work?". I agree that this post contained multiple questions and it might not be clear which one is the main one.  
  > **username_3**: For me, it's obvious that the main one is not "does the schema theorem have a proof?", but "what is the proof?". That's obvious because it's implied by the question "Why does this inequality hold?" The OP will eventually clarify what the main question is after having seen these comments.  
  > **username_3**: @username_2 In any case, I think this is one of the most fundamental questions that could have been asked here. So, voting to close this question for me is not the right thing to do, as the main question to me is obvious. There are examples of many other questions that should have been closed, if you want to vote to close them. For example, [this](https://ai.stackexchange.com/q/34184/2444).  
  > **username_2**: @username_3 if the main question is obvious to you, then kindly **edit** the question to remove any ambiguities (as I have explicitly suggested in my close vote). I can't see how "*this is one of the most fundamental questions that could have been asked here*" - anyone understanding the meaning of the term "*theorem*" is aware that there *is* a proof, and it is findable, for anyone really interested.  
  > **username_2**: And bold in itself says nothing; the last sentence was also in bold, which I edited out myself.  
  > **username_3**: Let us [continue this discussion in chat](https://chat.stackexchange.com/rooms/133314/discussion-between-username_3-and-username_2).  
  
  ---
  
  ## 0 answers
  
  