I am trying to implement GEP in common lisp. One of the main points is
the way the chromosome is decoded. Such that given a chromosome:
(+ Q - / b * a a Q b a a b a a b b a a a b)
where Q refers to square root and that + / - * have an arity of 2
while Q has 1. Also a and b are variables. The decoding starts with
the first element as the root, and then proceeds from left to right of
the chromosomes until all the final nodes are variables. Whatever
remains is discarded during fitness testing(but is still considered
part of the chromosome).
http://www.gene-expression-programming.com/Tutorial001.asp#TheArchitectureOfGEPPrograms
Thus for the chromosome above we would have:
(+ (sqrt (/ a a)) (- b (* (sqrt a) b))).
any suggestions on how to iterate through the chromosome?
Thanks in advance
In article
<····································@p31g2000prf.googlegroups.com>,
h2s <··········@gmail.com> wrote:
> I am trying to implement GEP in common lisp. One of the main points is
> the way the chromosome is decoded. Such that given a chromosome:
> (+ Q - / b * a a Q b a a b a a b b a a a b)
> where Q refers to square root and that + / - * have an arity of 2
> while Q has 1. Also a and b are variables. The decoding starts with
> the first element as the root, and then proceeds from left to right of
> the chromosomes until all the final nodes are variables. Whatever
> remains is discarded during fitness testing(but is still considered
> part of the chromosome).
>
> http://www.gene-expression-programming.com/Tutorial001.asp#TheArchitectureOfGEPPrograms
>
> Thus for the chromosome above we would have:
> (+ (sqrt (/ a a)) (- b (* (sqrt a) b))).
>
> any suggestions on how to iterate through the chromosome?
> Thanks in advance
In Lisp it is best do iterate from first to last.
--
http://lispm.dyndns.org/
h2s <··········@gmail.com> writes:
> I am trying to implement GEP in common lisp. One of the main points is
> the way the chromosome is decoded. Such that given a chromosome:
> (+ Q - / b * a a Q b a a b a a b b a a a b)
> where Q refers to square root and that + / - * have an arity of 2
> while Q has 1. Also a and b are variables. The decoding starts with
> the first element as the root, and then proceeds from left to right of
> the chromosomes until all the final nodes are variables. Whatever
> remains is discarded during fitness testing(but is still considered
> part of the chromosome).
>
> http://www.gene-expression-programming.com/Tutorial001.asp#TheArchitectureOfGEPPrograms
>
> Thus for the chromosome above we would have:
> (+ (sqrt (/ a a)) (- b (* (sqrt a) b))).
What rule do you use? In the following, I'll use Polish notation.
> any suggestions on how to iterate through the chromosome?
> Thanks in advance
You don't want to iterate thru it, you want to recurse through it.
(defvar *arities* '((+ . 2) (- . 2) (* . 2) (/ . 2) (Q . 1)))
(defun build-sexp (chro remainder)
(let ((arity (or (cdr (assoc (car chro) *arities*)) 0)))
(case arity
((0) (funcall remainder (car chro) (cdr chro)))
((1) (build-sexp (cdr chro)
(lambda (subexpr chro)
(funcall remainder `(sqrt ,subexpr) chro))))
((2) (let ((op (car chro)))
(build-sexp (cdr chro)
(lambda (subexpr1 chro)
(build-sexp chro
(lambda (subexpr2 chro)
(funcall remainder
`(,op ,subexpr1 ,subexpr2) chro)))))))
(otherwise (error "Arity not considered ~A/~A" (car chro) arity)))))
(build-sexp '(+ Q - / b * a a Q b a a b a a b b a a a b)
(lambda (expr chro) (print expr) (print chro)))
prints:
(+ (SQRT (- (/ B (* A A)) (SQRT B))) A)
(A B A A B B A A A B)
--
__Pascal Bourguignon__ http://www.informatimago.com/
"Specifications are for the weak and timid!"
On Aug 25, 3:47 pm, ····@informatimago.com (Pascal J. Bourguignon)
wrote:
> h2s <··········@gmail.com> writes:
> > I am trying to implement GEP in common lisp. One of the main points is
> > the way the chromosome is decoded. Such that given a chromosome:
> > (+ Q - / b * a a Q b a a b a a b b a a a b)
> > where Q refers to square root and that + / - * have an arity of 2
> > while Q has 1. Also a and b are variables. The decoding starts with
> > the first element as the root, and then proceeds from left to right of
> > the chromosomes until all the final nodes are variables. Whatever
> > remains is discarded during fitness testing(but is still considered
> > part of the chromosome).
>
> >http://www.gene-expression-programming.com/Tutorial001.asp#TheArchite...
>
> > Thus for the chromosome above we would have:
> > (+ (sqrt (/ a a)) (- b (* (sqrt a) b))).
>
> What rule do you use? In the following, I'll use Polish notation.
>
> > any suggestions on how to iterate through the chromosome?
> > Thanks in advance
>
> You don't want to iterate thru it, you want to recurse through it.
>
> (defvar *arities* '((+ . 2) (- . 2) (* . 2) (/ . 2) (Q . 1)))
> (defun build-sexp (chro remainder)
> (let ((arity (or (cdr (assoc (car chro) *arities*)) 0)))
> (case arity
> ((0) (funcall remainder (car chro) (cdr chro)))
> ((1) (build-sexp (cdr chro)
> (lambda (subexpr chro)
> (funcall remainder `(sqrt ,subexpr) chro))))
> ((2) (let ((op (car chro)))
> (build-sexp (cdr chro)
> (lambda (subexpr1 chro)
> (build-sexp chro
> (lambda (subexpr2 chro)
> (funcall remainder
> `(,op ,subexpr1 ,subexpr2) chro)))))))
> (otherwise (error "Arity not considered ~A/~A" (car chro) arity)))))
>
> (build-sexp '(+ Q - / b * a a Q b a a b a a b b a a a b)
> (lambda (expr chro) (print expr) (print chro)))
> prints:
> (+ (SQRT (- (/ B (* A A)) (SQRT B))) A)
> (A B A A B B A A A B)
>
> --
> __Pascal Bourguignon__ http://www.informatimago.com/
>
> "Specifications are for the weak and timid!"
First,thanks for your response.Secondly this is not a homework(not
intended to be rude).the inventor of GEP calls the decoding Karva
Language.in it we set the first element as the root of an expression
tree,then we transverse the chromosome from the second element
satisfying the arity of the previous node,taking whatever follows in
the chromosome.as shown in the tree below(taken form Gene Expression
Programming: a New Adaptive Algorithm for Solving Problems by Cândida
Ferreira).
+
/ \
/ \
Q -
| / \
Div b *
/ \ / \
/ \ Q b
a a |
a
There is a freely available C++ and python code,but i would like to
implement it in lisp.
again thanks
h2s <··········@gmail.com> writes:
> On Aug 25, 3:47�pm, ····@informatimago.com (Pascal J. Bourguignon)
> wrote:
>> h2s <··········@gmail.com> writes:
>> > I am trying to implement GEP in common lisp. One of the main points is
>> > the way the chromosome is decoded. Such that given a chromosome:
>> > (+ Q - / b * a a Q b a a b a a b b a a a b)
>> > �where Q refers to square root and that + / - * �have an arity of 2
>> > while Q has 1. Also a and b are variables. The decoding starts with
>> > the first element as the root, and then proceeds from left to right of
>> > the chromosomes until all the final nodes are variables. Whatever
>> > remains is discarded during fitness testing(but is still considered
>> > part of the chromosome).
>>
>> >http://www.gene-expression-programming.com/Tutorial001.asp#TheArchite...
>>
>> > �Thus for the chromosome �above we would have:
>> > (+ (sqrt (/ a a)) (- b (* (sqrt a) b))).
>>
>> What rule do you use? �In the following, I'll use Polish notation.
>>
>> > any suggestions on how to iterate through the chromosome?
>> > Thanks in advance
>>
>> You don't want to iterate thru it, you want to recurse through it.
> [...]
>
> First,thanks for your response.Secondly this is not a homework(not
> intended to be rude).the inventor of GEP calls the decoding Karva
> Language.in it we set the first element as the root of an expression
> tree,then we transverse the chromosome from the second element
> satisfying the arity of the previous node,taking whatever follows in
> the chromosome.as shown in the tree below(taken form Gene Expression
> Programming: a New Adaptive Algorithm for Solving Problems by C�ndida
> Ferreira).
> +
> / \
> / \
> Q -
> | / \
> Div b *
> / \ / \
> / \ Q b
> a a |
> a
I see, this is a breadth-first walk of the tree. I assume it has
better GP properties than a mere prefix.
There's a solution similar to my build-expr, just changing the order
of some calls.
Otherwise, a normal breadth-first tree building procedure is in order.
--
__Pascal Bourguignon__
···@informatimago.com (Pascal J. Bourguignon) writes:
> h2s <··········@gmail.com> writes:
>
>> On Aug 25, 3:47�pm, ····@informatimago.com (Pascal J. Bourguignon)
>> wrote:
>>> h2s <··········@gmail.com> writes:
>>> > I am trying to implement GEP in common lisp. One of the main points is
>>> > the way the chromosome is decoded. Such that given a chromosome:
>>> > (+ Q - / b * a a Q b a a b a a b b a a a b)
>>> > �Thus for the chromosome �above we would have:
>>> > (+ (sqrt (/ a a)) (- b (* (sqrt a) b))).
>>>
>> +
>> / \
>> / \
>> Q -
>> | / \
>> Div b *
>> / \ / \
>> / \ Q b
>> a a |
>> a
>
> I see, this is a breadth-first walk of the tree. I assume it has
> better GP properties than a mere prefix.
>
> There's a solution similar to my build-expr, just changing the order
> of some calls.
>
> Otherwise, a normal breadth-first tree building procedure is in order.
Like this:
(defun build-breadth-tree (get-node add-child)
"
GET-NODE: A function with no argument that must return two values,
the next node, and its arity.
ADD-CHILD: (add-child node subnode) must attach subnode as the last
child of node.
RETURN: The tree built from the breadth-first-walk returned by GET-NODE.
"
(multiple-value-bind (root arity) (funcall get-node)
(when (plusp arity)
(loop
:with unfilled-nodes = (list (list root arity))
:while unfilled-nodes
:do (loop
:with new-unfilled-nodes = '()
:for (node arity) :in unfilled-nodes
:do (loop
:repeat arity
:do (multiple-value-bind (subnode subarity) (funcall get-node)
(funcall add-child node subnode)
(when (plusp subarity)
(push (list subnode subarity) new-unfilled-nodes))))
:finally (setf unfilled-nodes (nreverse new-unfilled-nodes)))))
root))
(defparameter *arities* '((+ + 2) (- - 2) (* * 2) (/ / 2) (Q sqrt 1)))
(let ((bfw '(+ Q - / b * a a Q b a a b a a b b a a a b)))
(build-breadth-tree
(lambda ()
(let* ((node (pop bfw))
(arity (or (third (assoc node *arities*)) 0))
(fun (second (assoc node *arities*)))) ; try that in scheme! ;-)
(values (if (zerop arity) node (list fun))
arity)))
(lambda (node subnode)
(nconc node (list subnode)))))
--
__Pascal Bourguignon__
On Aug 25, 9:24 pm, ····@informatimago.com (Pascal J. Bourguignon)
wrote:
> ····@informatimago.com (Pascal J. Bourguignon) writes:
>
>
>
> > h2s <··········@gmail.com> writes:
>
> >> On Aug 25, 3:47 pm, ····@informatimago.com (Pascal J. Bourguignon)
> >> wrote:
> >>> h2s <··········@gmail.com> writes:
> >>> > I am trying to implement GEP in common lisp. One of the main points is
> >>> > the way the chromosome is decoded. Such that given a chromosome:
> >>> > (+ Q - / b * a a Q b a a b a a b b a a a b)
> >>> > Thus for the chromosome above we would have:
> >>> > (+ (sqrt (/ a a)) (- b (* (sqrt a) b))).
>
> >> +
> >> / \
> >> / \
> >> Q -
> >> | / \
> >> Div b *
> >> / \ / \
> >> / \ Q b
> >> a a |
> >> a
>
> > I see, this is a breadth-first walk of the tree. I assume it has
> > better GP properties than a mere prefix.
>
> > There's a solution similar to my build-expr, just changing the order
> > of some calls.
>
> > Otherwise, a normal breadth-first tree building procedure is in order.
>
> Like this:
>
> (defun build-breadth-tree (get-node add-child)
> "
> GET-NODE: A function with no argument that must return two values,
> the next node, and its arity.
> ADD-CHILD: (add-child node subnode) must attach subnode as the last
> child of node.
> RETURN: The tree built from the breadth-first-walk returned by GET-NODE.
> "
> (multiple-value-bind (root arity) (funcall get-node)
> (when (plusp arity)
> (loop
> :with unfilled-nodes = (list (list root arity))
> :while unfilled-nodes
> :do (loop
> :with new-unfilled-nodes = '()
> :for (node arity) :in unfilled-nodes
> :do (loop
> :repeat arity
> :do (multiple-value-bind (subnode subarity) (funcall get-node)
> (funcall add-child node subnode)
> (when (plusp subarity)
> (push (list subnode subarity) new-unfilled-nodes))))
> :finally (setf unfilled-nodes (nreverse new-unfilled-nodes)))))
> root))
>
> (defparameter *arities* '((+ + 2) (- - 2) (* * 2) (/ / 2) (Q sqrt 1)))
> (let ((bfw '(+ Q - / b * a a Q b a a b a a b b a a a b)))
> (build-breadth-tree
> (lambda ()
> (let* ((node (pop bfw))
> (arity (or (third (assoc node *arities*)) 0))
> (fun (second (assoc node *arities*)))) ; try that in scheme! ;-)
> (values (if (zerop arity) node (list fun))
> arity)))
> (lambda (node subnode)
> (nconc node (list subnode)))))
>
> --
> __Pascal Bourguignon__
thanks,i have tested the code on different chromosomes and gives the
expressions as explained in GEP.
In article <··············@hubble.informatimago.com>,
···@informatimago.com (Pascal J. Bourguignon) wrote:
> h2s <··········@gmail.com> writes:
>
> > I am trying to implement GEP in common lisp. One of the main points is
> > the way the chromosome is decoded. Such that given a chromosome:
> > (+ Q - / b * a a Q b a a b a a b b a a a b)
> > where Q refers to square root and that + / - * have an arity of 2
> > while Q has 1. Also a and b are variables. The decoding starts with
> > the first element as the root, and then proceeds from left to right of
> > the chromosomes until all the final nodes are variables. Whatever
> > remains is discarded during fitness testing(but is still considered
> > part of the chromosome).
> >
> > http://www.gene-expression-programming.com/Tutorial001.asp#TheArchitectureOfGEPPrograms
> >
> > Thus for the chromosome above we would have:
> > (+ (sqrt (/ a a)) (- b (* (sqrt a) b))).
>
> What rule do you use? In the following, I'll use Polish notation.
>
>
> > any suggestions on how to iterate through the chromosome?
> > Thanks in advance
>
> You don't want to iterate thru it, you want to recurse through it.
>
> (defvar *arities* '((+ . 2) (- . 2) (* . 2) (/ . 2) (Q . 1)))
> (defun build-sexp (chro remainder)
> (let ((arity (or (cdr (assoc (car chro) *arities*)) 0)))
> (case arity
> ((0) (funcall remainder (car chro) (cdr chro)))
> ((1) (build-sexp (cdr chro)
> (lambda (subexpr chro)
> (funcall remainder `(sqrt ,subexpr) chro))))
> ((2) (let ((op (car chro)))
> (build-sexp (cdr chro)
> (lambda (subexpr1 chro)
> (build-sexp chro
> (lambda (subexpr2 chro)
> (funcall remainder
> `(,op ,subexpr1 ,subexpr2) chro)))))))
> (otherwise (error "Arity not considered ~A/~A" (car chro) arity)))))
>
>
> (build-sexp '(+ Q - / b * a a Q b a a b a a b b a a a b)
> (lambda (expr chro) (print expr) (print chro)))
> prints:
> (+ (SQRT (- (/ B (* A A)) (SQRT B))) A)
> (A B A A B B A A A B)
Pascal, that's evil. You are solving every homework. Instructors
will switch away from Lisp.
--
http://lispm.dyndns.org/
h2s schrieb:
> I am trying to implement GEP in common lisp.
It�s a nice training to implement it and can be fun to experiment
with it. Although you didn�t ask for it I just would like to mention
that GEP is not so special as miss Ferreira wants to make us believe.
Especially she often pronouces that GEP is so much better than GP
(Genetic Programming), which is not true.
In fact I am not even sure if GEP usually performs equally well for
most problems, but instead a little bit worse.
She did not understand that she made several mistakes in her measurement
and that�s why she thought in her early trials that she really dis-
covered anything new. GEP is still GP.
Andr�
--
I don’t really understand why complete no ones feel compelled to bad
mouth other peoples work in public. If you disagree with her work and
conclusions write a paper and have it reviewed and published like she
did.
··········@googlemail.com writes:
> I don’t really understand why complete no ones feel compelled to bad
> mouth other peoples work in public. If you disagree with her work and
> conclusions write a paper and have it reviewed and published like she
> did.
I hope André will take up the gauntlet and write this paper!
--
__Pascal Bourguignon__
Pascal J. Bourguignon schrieb:
> ··········@googlemail.com writes:
>
>> I don’t really understand why complete no ones feel compelled to bad
>> mouth other peoples work in public. If you disagree with her work and
>> conclusions write a paper and have it reviewed and published like she
>> did.
>
> I hope André will take up the gauntlet and write this paper!
There is no need for it, because it was already done.
Experts in the area of Genetic Programming pointed out several problem
in Ferreira works. The regarding yahoo news group has also lots of
comments in its archive, even from John Koza himself.
I just mentioned it here because the poster “h2s” might be new to these
programming techniques and might believe Ferreiras claims, like that
“GEP surpasses the old GP technique by a factor of 100-60,000”.
I went through her book where she showed that even very small populations
came to results for which GP needed much bigger populations.
But funnily this is not true. She worked on the examples that Koza
gave in his book. He made totally clear that the point of his book was
to show in a scientific way that GP works. For that he used the same
parameters for each run in his book and never optimized it.
Ferraira however used only extremly small chromosomes.
I don’t have the tutorial at hands right now, but let’s say the
chromosome size was 20. It doesn’t matter if it was 10, 20 or even
100. The problem is that if you convert this into a tree it can have
a maximum of 20 (or 100) points, be it functions or terminals.
Koza on the other hand used throughout his book a maximum depth
after crossover of 17. This means the programs his GP system created
could possibly grow up to (2ˆ17)-1 points, which is around 130.000.
So, we have a program of a maximum length of 20 lines of code versus
a program of up to 130.000 LOC. It is obvious that the search space
that Koza used (only for scientifically reasons) was much bigger.
When I did the same examples that Ferreira did, but with her parameter
settings adopted for GP I “magically” got the same results.
But even if this is not done GP several times outperforms GEP.
In one case in the yahoo group someone used 500 individuals (GP) and
compared it to the same problem as Ferreira with GEP, with only 50
individuals. They got basically the same results, only that GP got it
after 23 generations while GEP needed 923 generations.
That’s a total of 11500 programs for GEP and 46150 for GEP.
But if GEP would indeed surpass GP by a factor of 100 (and that is the
smallest number Ferreira claims) GEP should have only needed 115
individuals.
That’s 3 generations, not 923.
As I said, I did several experiments from Ferreiras book, but this time
using her parameters which were adopted to solve the problem fast,
instead of Kozas approach, who wanted to show scientifically that GP
indeed works. I found no evidence at all that GEP performs better in
any way.
And the explanation for that is very simple. Ferreira has a background
in biology. She ignored the mathematical facts about bijections.
What she does is basically take a GP tree (in that sense: a lisp
program) and writes it down in another form, the so called K-expression,
which is usually nothing but a string.
This is what h2s presented us in his OP, although he/she used lists
instead.
This K-expression is then manipulated. In GP this manipulation happens
directly on the program tree itself. Now Ferreira believes that if she
manipulates the same tree when it was coded in a different data format,
a string, and then shuffles around chars in this string and forms it
back to a tree to execute it, that this will somehow bring things to
evolve faster.
She could not show this in any paper. It’s still she who first needs
to bring a proof for her claim. Of course, as her kexp is nothing but
a simple bijection any operation that can be done on the kexp can also
be done on a sexp.
But really, I suppose that in fact her operations are more random than
those that are used in GP. So, GEP does much more often what would be
considered a secondary operation in GP, similar to mutation.
This is not only my understanding about it, but also the big names in
that field like John Koza, Sean Luke or Conor Ryan do and they wrote
about it for example in the yahoo group:
http://tech.groups.yahoo.com/group/genetic_programming/
Ferreira also basically copied parts of work which Conor Ryan and his
team developed, a method called Grammatical Evolution, but sadly she
didn’t cite that work and tries to sell it to us as her idea.
Also about papers: when Ferreira sent her papers to real authorities
in the area, like John Koza, her papers were rejected.
For more about this read Ferrairas official FAQ:
http://www.gene-expression-programming.com/Q&A03.asp#PersCorr23
At Rod Bartol: I find it funny that you jump into a discussion with your
meta criticism, as if you would know anything about the GP/GEP
controversial.
I just wanted to inform a newcomer to GEP that the claims of Ferraira
are not true (were not proven, while evidence support that her claims
are probably not true).
André
--
On Aug 29, 2:19 pm, André Thieme <address.good.until.
···········@justmail.de> wrote:
> Pascal J. Bourguignon schrieb:
>
> > ··········@googlemail.com writes:
>
> >> I don’t really understand why complete no ones feel compelled to bad
> >> mouth other peoples work in public. If you disagree with her work and
> >> conclusions write a paper and have it reviewed and published like she
> >> did.
>
> > I hope André will take up the gauntlet and write this paper!
>
> There is no need for it, because it was already done.
> Experts in the area of Genetic Programming pointed out several problem
> in Ferreira works. The regarding yahoo news group has also lots of
> comments in its archive, even from John Koza himself.
>
> I just mentioned it here because the poster “h2s” might be new to these
> programming techniques and might believe Ferreiras claims, like that
> “GEP surpasses the old GP technique by a factor of 100-60,000”.
>
> I went through her book where she showed that even very small populations
> came to results for which GP needed much bigger populations.
> But funnily this is not true. She worked on the examples that Koza
> gave in his book. He made totally clear that the point of his book was
> to show in a scientific way that GP works. For that he used the same
> parameters for each run in his book and never optimized it.
> Ferraira however used only extremly small chromosomes.
> I don’t have the tutorial at hands right now, but let’s say the
> chromosome size was 20. It doesn’t matter if it was 10, 20 or even
> 100. The problem is that if you convert this into a tree it can have
> a maximum of 20 (or 100) points, be it functions or terminals.
> Koza on the other hand used throughout his book a maximum depth
> after crossover of 17. This means the programs his GP system created
> could possibly grow up to (2ˆ17)-1 points, which is around 130.000.
> So, we have a program of a maximum length of 20 lines of code versus
> a program of up to 130.000 LOC. It is obvious that the search space
> that Koza used (only for scientifically reasons) was much bigger.
>
> When I did the same examples that Ferreira did, but with her parameter
> settings adopted for GP I “magically” got the same results.
> But even if this is not done GP several times outperforms GEP.
> In one case in the yahoo group someone used 500 individuals (GP) and
> compared it to the same problem as Ferreira with GEP, with only 50
> individuals. They got basically the same results, only that GP got it
> after 23 generations while GEP needed 923 generations.
> That’s a total of 11500 programs for GEP and 46150 for GEP.
> But if GEP would indeed surpass GP by a factor of 100 (and that is the
> smallest number Ferreira claims) GEP should have only needed 115
> individuals.
> That’s 3 generations, not 923.
> As I said, I did several experiments from Ferreiras book, but this time
> using her parameters which were adopted to solve the problem fast,
> instead of Kozas approach, who wanted to show scientifically that GP
> indeed works. I found no evidence at all that GEP performs better in
> any way.
>
> And the explanation for that is very simple. Ferreira has a background
> in biology. She ignored the mathematical facts about bijections.
> What she does is basically take a GP tree (in that sense: a lisp
> program) and writes it down in another form, the so called K-expression,
> which is usually nothing but a string.
> This is what h2s presented us in his OP, although he/she used lists
> instead.
> This K-expression is then manipulated. In GP this manipulation happens
> directly on the program tree itself. Now Ferreira believes that if she
> manipulates the same tree when it was coded in a different data format,
> a string, and then shuffles around chars in this string and forms it
> back to a tree to execute it, that this will somehow bring things to
> evolve faster.
> She could not show this in any paper. It’s still she who first needs
> to bring a proof for her claim. Of course, as her kexp is nothing but
> a simple bijection any operation that can be done on the kexp can also
> be done on a sexp.
>
> But really, I suppose that in fact her operations are more random than
> those that are used in GP. So, GEP does much more often what would be
> considered a secondary operation in GP, similar to mutation.
> This is not only my understanding about it, but also the big names in
> that field like John Koza, Sean Luke or Conor Ryan do and they wrote
> about it for example in the yahoo group:http://tech.groups.yahoo.com/group/genetic_programming/
>
> Ferreira also basically copied parts of work which Conor Ryan and his
> team developed, a method called Grammatical Evolution, but sadly she
> didn’t cite that work and tries to sell it to us as her idea.
>
> Also about papers: when Ferreira sent her papers to real authorities
> in the area, like John Koza, her papers were rejected.
> For more about this read Ferrairas official FAQ:http://www.gene-expression-programming.com/Q&A03.asp#PersCorr23
>
> At Rod Bartol: I find it funny that you jump into a discussion with your
> meta criticism, as if you would know anything about the GP/GEP
> controversial.
> I just wanted to inform a newcomer to GEP that the claims of Ferraira
> are not true (were not proven, while evidence support that her claims
> are probably not true).
>
> André
> --
Thanks also for the information.do you object to her naming it GEP or
to the methodology and algorithm she use?am still a newcomer as you
said.
h2s schrieb:
> Thanks also for the information.do you object to her naming it GEP or
> to the methodology and algorithm she use?am still a newcomer as you
> said.
In my opinion it�s okay that she names it like this, although I see that
it could confuse people. But everyone who works in this field will
sooner or later learn about the differences.
GEP works, no question. It just is GP with some extra step.
It converts a tree (if doing GP in Lisp then tree means a program in
that case) into another representation on which the genetic operations
are then performed. To test the programs they have to be converted back
into tree form and then get evaluated (in GEP).
My only point is that I see not why the claim that GEP works 100-60k
times �better� than GP, only because the genetic operations are not done
on the tree itself.
We could as well use WinRAR to pack a lisp program, then shuffle the
letters in the .rar file around and unpack it back to a Lisp program and
expect it to evolve dramatically much faster as it would if you manipulate
the tree directly, as it happens in GP.
Okay, I admit that .rar files are a bad example here because one couldn�t
unpack a randomly changed file back to a working Lisp program, but you
got the idea.
I personally suggest to at least think about getting the books of John
Koza who is one of the leading experts in the world in the area of
Genetic Programming (not really the inventor, but most people regard
him more or less like that). Plus he writes his books in a style so that
even mortals can understand him. He does not try to seem extremly clever
by using complicated descriptions that only a few people could decipher.
Very good job in writing books.
One just needs a background in thinking and it�ll be good ;-)
Andr�
--
André Thieme <······························@justmail.de> writes:
> Pascal J. Bourguignon schrieb:
>> ··········@googlemail.com writes:
>>
>>> I don’t really understand why complete no ones feel compelled to bad
>>> mouth other peoples work in public. If you disagree with her work and
>>> conclusions write a paper and have it reviewed and published like she
>>> did.
>> I hope André will take up the gauntlet and write this paper!
>
>
> There is no need for it, because it was already done.
> Experts in the area of Genetic Programming pointed out several problem
> in Ferreira works. The regarding yahoo news group has also lots of
> comments in its archive, even from John Koza himself.
>
> I just mentioned it here because the poster “h2s” might be new to these
> programming techniques and might believe Ferreiras claims, like that
> “GEP surpasses the old GP technique by a factor of 100-60,000”.
>
> I went through her book where she showed that even very small populations
> came to results for which GP needed much bigger populations.
> But funnily this is not true. She worked on the examples that Koza
> gave in his book. He made totally clear that the point of his book was
> to show in a scientific way that GP works. For that he used the same
> parameters for each run in his book and never optimized it.
> Ferraira however used only extremly small chromosomes.
> I don’t have the tutorial at hands right now, but let’s say the
> chromosome size was 20. It doesn’t matter if it was 10, 20 or even
> 100. The problem is that if you convert this into a tree it can have
> a maximum of 20 (or 100) points, be it functions or terminals.
> Koza on the other hand used throughout his book a maximum depth
> after crossover of 17. This means the programs his GP system created
> could possibly grow up to (2ˆ17)-1 points, which is around 130.000.
> So, we have a program of a maximum length of 20 lines of code versus
> a program of up to 130.000 LOC. It is obvious that the search space
> that Koza used (only for scientifically reasons) was much bigger.
>
> When I did the same examples that Ferreira did, but with her parameter
> settings adopted for GP I “magically” got the same results.
> But even if this is not done GP several times outperforms GEP.
> In one case in the yahoo group someone used 500 individuals (GP) and
> compared it to the same problem as Ferreira with GEP, with only 50
> individuals. They got basically the same results, only that GP got it
> after 23 generations while GEP needed 923 generations.
> That’s a total of 11500 programs for GEP and 46150 for GEP.
> But if GEP would indeed surpass GP by a factor of 100 (and that is the
> smallest number Ferreira claims) GEP should have only needed 115
> individuals.
> That’s 3 generations, not 923.
> As I said, I did several experiments from Ferreiras book, but this time
> using her parameters which were adopted to solve the problem fast,
> instead of Kozas approach, who wanted to show scientifically that GP
> indeed works. I found no evidence at all that GEP performs better in
> any way.
>
> And the explanation for that is very simple. Ferreira has a background
> in biology. She ignored the mathematical facts about bijections.
> What she does is basically take a GP tree (in that sense: a lisp
> program) and writes it down in another form, the so called K-expression,
> which is usually nothing but a string.
> This is what h2s presented us in his OP, although he/she used lists
> instead.
> This K-expression is then manipulated. In GP this manipulation happens
> directly on the program tree itself. Now Ferreira believes that if she
> manipulates the same tree when it was coded in a different data format,
> a string, and then shuffles around chars in this string and forms it
> back to a tree to execute it, that this will somehow bring things to
> evolve faster.
> She could not show this in any paper. It’s still she who first needs
> to bring a proof for her claim. Of course, as her kexp is nothing but
> a simple bijection any operation that can be done on the kexp can also
> be done on a sexp.
>
> But really, I suppose that in fact her operations are more random than
> those that are used in GP. So, GEP does much more often what would be
> considered a secondary operation in GP, similar to mutation.
> This is not only my understanding about it, but also the big names in
> that field like John Koza, Sean Luke or Conor Ryan do and they wrote
> about it for example in the yahoo group:
> http://tech.groups.yahoo.com/group/genetic_programming/
>
> Ferreira also basically copied parts of work which Conor Ryan and his
> team developed, a method called Grammatical Evolution, but sadly she
> didn’t cite that work and tries to sell it to us as her idea.
>
> Also about papers: when Ferreira sent her papers to real authorities
> in the area, like John Koza, her papers were rejected.
> For more about this read Ferrairas official FAQ:
> http://www.gene-expression-programming.com/Q&A03.asp#PersCorr23
>
> At Rod Bartol: I find it funny that you jump into a discussion with your
> meta criticism, as if you would know anything about the GP/GEP
> controversial.
> I just wanted to inform a newcomer to GEP that the claims of Ferraira
> are not true (were not proven, while evidence support that her claims
> are probably not true).
>
>
> André
Thanks for this report. ;-)
--
__Pascal Bourguignon__
I maintain my criticism of your post. Citing newsgroups and private
experiments is not enough to support your claims. All I can gleam from
the links you provide is that the paper wasn't accepted straightaway
but it did end up being published in a peer reviewed scientific
journal. So it was indeed reviewed and accepted by experts. I guess
that an outsider always has problems publishing no matter what the
field is.
What I don’t understand is what is your motivation to, after some 7 or
8 years where dozens of papers and several books about GEP have been
published by different people, jump in and summarily dismiss somebody
else’s work with not much more to show than a few newsgroups rants.
And for all I know your experiments may be completely flawed, at least
hers are out there for everyone to criticize.
··········@googlemail.com schrieb:
> I maintain my criticism of your post. Citing newsgroups and private
> experiments is not enough to support your claims.
I also told you that you need to adopt the maximum depth after crossovers
to do it the same way Ferreira did.
This is a newsgroup and not a science discussion board. In a newsgroup
it�s more than enough what I did. Better you sit down and try to
set the parameters as Ferreira did it in your GP system and test it
yourself. It�s very easy to reproduce.
> All I can gleam from
> the links you provide is that the paper wasn't accepted straightaway
> but it did end up being published in a peer reviewed scientific
> journal. So it was indeed reviewed and accepted by experts. I guess
> that an outsider always has problems publishing no matter what the
> field is.
GEP is in fact GP undercover. And the experts in that area can
tell you. Of course GEP works. And just tell me who the experts were
who reviewed her work. Tell me the source whe she proved scientifically
that GEP outperforms GP by a factor of 100-60.000 please and what experts
agree with it.
> What I don�t understand is what is your motivation to, after some 7 or
> 8 years where dozens of papers and several books about GEP have been
> published by different people, jump in and summarily dismiss somebody
> else�s work with not much more to show than a few newsgroups rants.
> And for all I know your experiments may be completely flawed, at least
> hers are out there for everyone to criticize.
Since hundreds of years there are books, also supported by great scientists
that prove the existance of God.
GEP works, of course, that is not the question. The performance claims
are the problem. There is a lot of stuff out there which is supported
by some people, but that still doesn�t mean that Ferreiras claims are
true.
See, you have not shown any evidence that you know much about GP or
GEP. You jump into a newgroup and do your meta criticism to me who has
actually seen no proof, worked with GP and GEP and also tried to start
a discussion with Ferreira. It still is her who needs to prove.
I agree that in my first posting I also put not much evidence for my
background. I can understand that if you are used to discussions in
a university that this would not be acceptable. Only that I post it at
home, in my freetime. And I know what I am talking about.
Andr�
--
On Fri, 29 Aug 2008 08:19:48 +0200, <······························@justmail.de> wrote:
> Pascal J. Bourguignon schrieb:
>> ··········@googlemail.com writes:
>>
>>> I don?t really understand why complete no ones feel compelled to bad
>>> mouth other peoples work in public. If you disagree with her work and
>>> conclusions write a paper and have it reviewed and published like she
>>> did.
>
> There is no need for it, because it was already done.
> Experts in the area of Genetic Programming pointed out several problem
> in Ferreira works.
Since she has discarded the tree structure for a list, an immediate
flaw is when a randomization of that list produces a bad case. That
would be where the 'square-root' is at the end of the list without
anything to operate on. The tree structure ensures that no bad cases
can exist. Putting some rules in to prevent bad cases in the list
form means you NEVER get close to the tree solution speed (that very
problem was why I dumped perl and moved to lisp).
That a woman doesn't listen to criticism is hardly a surprise. Unless
she has some nice solution to the known problems of GP (being able to
simplify the resulting trees, recognizing subtrees as a new function
etc) then she is stuck with that perl group solving a curve fitting
problem. They never understood that there are an infinite set of
curves passing thru a set of discrete points.
--
One of the strokes of genius from McCarthy
was making lists the center of the language - kt
** Posted from http://www.teranews.com **