Linear genetic programming: Difference between revisions

From HandWiki
imported>Scavis2
add
 
AstroAI (talk | contribs)
0 edits
fixing
 
Line 2: Line 2:
:''"Linear genetic programming" is unrelated to "[[Linear programming|linear programming]]".''
:''"Linear genetic programming" is unrelated to "[[Linear programming|linear programming]]".''


'''Linear genetic programming''' (LGP)<ref name=book>M. Brameier, W. Banzhaf, "[https://link.springer.com/book/10.1007/978-0-387-31030-5 Linear Genetic Programming]", Springer, New York, 2007</ref> is a particular method of [[Genetic programming|genetic programming]] wherein computer programs in a population are represented as a sequence of instructions from an [[Imperative programming|imperative programming language]] or [[Machine code|machine language]]. The adjective "linear" stems from the fact that the sequence of instructions is normally executed in a linear fashion. Like in other programs, the data flow in LGP can be modeled as a graph that will visualize the potential multiple usage of [[Processor register|register]] contents and the existence of structurally noneffective code (introns) which are two main differences of this [[Genetic representation|genetic representation]] from the more common tree-based [[Genetic programming|genetic programming]] (TGP) variant.<ref name=Brameier>Brameier, M.: "[https://eldorado.uni-dortmund.de/handle/2003/20098 On linear genetic programming] {{webarchive|url=https://web.archive.org/web/20070629120053/https://eldorado.uni-dortmund.de/handle/2003/20098 |date=2007-06-29 }}", Dortmund, 2003</ref><ref>W. Banzhaf, P. Nordin, R. Keller, F. Francone, [https://www.amazon.com/Genetic-Programming-Introduction-Artificial-Intelligence/dp/155860510X Genetic Programming - An Introduction], Morgan Kaufmann, Heidelberg/San Francisco, 1998</ref>
'''Linear genetic programming''' (LGP)<ref name=book>M. Brameier, W. Banzhaf, "[https://link.springer.com/book/10.1007/978-0-387-31030-5 Linear Genetic Programming]", Springer, New York, 2007</ref> is a particular method of [[Genetic programming|genetic programming]] wherein computer programs in a population are represented as a sequence of register-based instructions from an [[Imperative programming|imperative programming language]] or [[Machine code|machine language]]. The adjective "linear" stems from the fact that each LGP program is a sequence of instructions and the sequence of instructions is normally executed sequentially. Like in other programs, the data flow in LGP can be modeled as a graph that will visualize the potential multiple usage of [[Processor register|register]] contents and the existence of structurally noneffective code (introns) which are two main differences of this [[Genetic representation|genetic representation]] from the more common tree-based [[Genetic programming|genetic programming]] (TGP) variant.<ref name=Brameier>Brameier, M.: "[https://eldorado.uni-dortmund.de/handle/2003/20098 On linear genetic programming] {{webarchive|url=https://web.archive.org/web/20070629120053/https://eldorado.uni-dortmund.de/handle/2003/20098 |date=2007-06-29 }}", Dortmund, 2003</ref><ref>W. Banzhaf, P. Nordin, R. Keller, F. Francone, [https://www.amazon.com/Genetic-Programming-Introduction-Artificial-Intelligence/dp/155860510X Genetic Programming - An Introduction], Morgan Kaufmann, Heidelberg/San Francisco, 1998</ref>
<ref>{{cite book | author1=Poli, R.|author2= Langdon, W. B.|author3= McPhee, N. F. |year=2008 |title=A Field Guide to Genetic Programming | url=https://archive.org/details/AFieldGuideToGeneticProgramming| publisher=Lulu.com, freely available from the internet | isbn = 978-1-4092-0073-4}}</ref>
<ref>{{cite book | author1=Poli, R.|author2= Langdon, W. B.|author3= McPhee, N. F. |year=2008 |title=A Field Guide to Genetic Programming | url=https://archive.org/details/AFieldGuideToGeneticProgramming| publisher=Lulu.com, freely available from the internet | isbn = 978-1-4092-0073-4}}</ref>


Like other Genetic Programming methods, '''Linear genetic programming''' requires the input of data to run the program population on. Then, the output of the program (its behaviour) is judged against some target behaviour, using a fitness function. However, LGP is generally more efficient than '''tree genetic programming''' due to its two main differences mentioned above: Intermediate results (stored in registers) can be reused and a simple intron removal algorithm exists<ref name=book/> that can be executed to remove all non-effective code prior to programs being run on the intended data. These two differences  often result in compact solutions and substantial computational savings compared to the highly constrained data flow in trees and the common method of executing all tree nodes in TGP.
Like other Genetic Programming methods, '''Linear genetic programming''' requires the input of data to run the program population on. Then, the output of the program (its behaviour) is judged against some target behaviour, using a fitness function. However, LGP is generally more efficient than '''tree genetic programming''' due to its two main differences mentioned above: Intermediate results (stored in registers) can be reused and a simple intron removal algorithm exists<ref name=book/> that can be executed to remove all non-effective code prior to programs being run on the intended data. These two differences  often result in compact solutions and substantial computational savings compared to the highly constrained data flow in trees and the common method of executing all tree nodes in TGP. Furthermore, LGP naturally has multiple outputs by defining multiple output registers and easily cooperates with [[Control flow|control flow operations]].


'''Linear genetic programming''' has been applied in many domains, including system modeling and system control with considerable success.<ref>M. Brameier, W. Banzhaf, [https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=7cb0f6755e325494afbda4f822026e8e6953ffe1 A Comparison of Linear Genetic Programming and Neural Networks in Medical Data Mining]", ''IEEE Transactions on Evolutionary Computation'', ''5'' (2001) 17-26</ref><ref>A. Guven, [https://link.springer.com/article/10.1007/s12040-009-0022-9 Linear genetic programming for time-series modelling of daily flow rate], ''J. Earth Systems Science'', ''118'' (2009) 137-146</ref><ref>R. Li, B.R. Noack, L. Cordier, J. Boree, F. Harambat, [https://link.springer.com/article/10.1007/s00348-017-2382-2 Drag reduction of a car model by linear genetic programming control], ''Experiments in Fluids'', ''58'' (2017) 103</ref><ref>P.-Y. Passagia, A. Quansah, N. Mazellier, G.Y. Cornejo Maceda, A. Kourta, [https://aip.scitation.org/doi/full/10.1063/5.0087874 Real-time feedback stall control of an airfoil at large Reynolds numbers using linear genetic programming], ''Physics of Fluids'', 34 (2022) 045108</ref>
'''Linear genetic programming''' has been applied in many domains, including system modeling and system control with considerable success.<ref>M. Brameier, W. Banzhaf, [https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=7cb0f6755e325494afbda4f822026e8e6953ffe1 A Comparison of Linear Genetic Programming and Neural Networks in Medical Data Mining]", ''IEEE Transactions on Evolutionary Computation'', ''5'' (2001) 17-26</ref><ref>A. Guven, [https://link.springer.com/article/10.1007/s12040-009-0022-9 Linear genetic programming for time-series modelling of daily flow rate], ''J. Earth Systems Science'', ''118'' (2009) 137-146</ref><ref>R. Li, B.R. Noack, L. Cordier, J. Boree, F. Harambat, [https://link.springer.com/article/10.1007/s00348-017-2382-2 Drag reduction of a car model by linear genetic programming control], ''Experiments in Fluids'', ''58'' (2017) 103</ref><ref>P.-Y. Passagia, A. Quansah, N. Mazellier, G.Y. Cornejo Maceda, A. Kourta, [https://aip.scitation.org/doi/full/10.1063/5.0087874 Real-time feedback stall control of an airfoil at large Reynolds numbers using linear genetic programming], ''Physics of Fluids'', 34 (2022) 045108</ref>


'''Linear genetic programming''' should not be confused with '''linear tree''' programs in tree genetic programming, program composed of a variable number of unary functions and a single [[Leaf node|terminal]]. Note that linear tree GP differs from bit string genetic algorithms since a population may contain programs of different lengths and there may be more than two types of functions or more than two types of terminals.<ref>
'''Linear genetic programming''' should not be confused with '''linear tree''' programs in tree genetic programming, program composed of a variable number of unary functions and a single [[Leaf node|terminal]]. Note that linear tree GP differs from bit string [[Genetic algorithms|genetic algorithms]] since a population may contain programs of different lengths and there may be more than two types of functions or more than two types of terminals.<ref>
[http://www.cs.ucl.ac.uk/staff/W.Langdon/FOGP/ Foundations of Genetic Programming].
[http://www.cs.ucl.ac.uk/staff/W.Langdon/FOGP/ Foundations of Genetic Programming].
</ref>
</ref>
Line 16: Line 16:


Because LGP programs are basically represented by a linear sequence of instructions, they are simpler to read and to operate on than their tree-based counterparts. For example, a simple program written to solve a Boolean function problem with 3 inputs (in R1, R2, R3) and one output (in R0), could read like this:
Because LGP programs are basically represented by a linear sequence of instructions, they are simpler to read and to operate on than their tree-based counterparts. For example, a simple program written to solve a Boolean function problem with 3 inputs (in R1, R2, R3) and one output (in R0), could read like this:
<source lang="bash">
<syntaxhighlight lang="bash">
R4 = R2 AND R3
R4 = R2 AND R3
R0 = R1 OR R4
R0 = R1 OR R4
Line 22: Line 22:
R4 = R2 AND R4  # This is a non-effective instruction
R4 = R2 AND R4  # This is a non-effective instruction
R0 = R0 OR R2
R0 = R0 OR R2
</source>
</syntaxhighlight>
R1, R2, R3 have to be declared as input (read-only) registers, while R0 and R4 are declared as calculation (read-write) registers. This program is very simple, having just 5 instructions. But mutation and crossover operators could work to increase the length of the program, as well as the content of each of its instructions.
R1, R2, R3 have to be declared as input (read-only) registers, while R0 and R4 are declared as calculation (read-write) registers. This program is very simple, having just 5 instructions. But mutation and crossover operators could work to increase the length of the program, as well as the content of each of its instructions.


Line 28: Line 28:


Another simple program, this one written in the LGP language [https://github.com/arturadib/slash-a Slash/A] looks like a series of instructions separated by a slash:
Another simple program, this one written in the LGP language [https://github.com/arturadib/slash-a Slash/A] looks like a series of instructions separated by a slash:
<source lang="bash">
<syntaxhighlight lang="bash">
input/  # gets an input from user and saves it to register F
input/  # gets an input from user and saves it to register F
0/      # sets register I = 0
0/      # sets register I = 0
Line 35: Line 35:
add/    # adds to F current data pointed to by I (i.e. F := F + D[0])
add/    # adds to F current data pointed to by I (i.e. F := F + D[0])
output/. # outputs result from F
output/. # outputs result from F
</source>
</syntaxhighlight>
By representing such code in [[Software:Bytecode|bytecode]] format, i.e. as an array of bytes each representing a different instruction, one can make [[Mutation (genetic algorithm)|mutation]] operations simply by changing an element of such an array.
By representing such code in [[Software:Bytecode|bytecode]] format, i.e. as an array of bytes each representing a different instruction, one can make [[Mutation (genetic algorithm)|mutation]] operations simply by changing an element of such an array.


Line 51: Line 51:
*[https://web.archive.org/web/20150801073202/http://digitalbiology.net/ DigitalBiology.NET] Vertical search engine for GA/GP resources
*[https://web.archive.org/web/20150801073202/http://digitalbiology.net/ DigitalBiology.NET] Vertical search engine for GA/GP resources
*[https://web.archive.org/web/20060816011453/http://www.aimlearning.com/ Discipulus] Genetic-Programming Software
*[https://web.archive.org/web/20060816011453/http://www.aimlearning.com/ Discipulus] Genetic-Programming Software
*[http://ugp3.sourceforge.net/ MicroGP] Genetic-Programming Software (open source)
*[https://ugp3.sourceforge.net/ MicroGP] Genetic-Programming Software (open source)
*[https://github.com/Zhixing1020/Linear-Genetic-Programming-LGP-and-Applications] An open-source Linear GP project based on a Java-based Evolutionary Computation Research System (ECJ).
*[http://www.genetic-programming.org ]
*[http://www.genetic-programming.org ]
{{Evolutionary computation}}
{{Evolutionary computation}}


[[Category:Genetic programming]]
[[Category:Genetic programming|#]]


{{Sourceattribution|Linear genetic programming}}
{{Sourceattribution|Linear genetic programming}}

Latest revision as of 13:30, 24 May 2026

Part of a series on the
Evolutionary algorithm
Genetic algorithm
Genetic programming
"Linear genetic programming" is unrelated to "linear programming".

Linear genetic programming (LGP)[1] is a particular method of genetic programming wherein computer programs in a population are represented as a sequence of register-based instructions from an imperative programming language or machine language. The adjective "linear" stems from the fact that each LGP program is a sequence of instructions and the sequence of instructions is normally executed sequentially. Like in other programs, the data flow in LGP can be modeled as a graph that will visualize the potential multiple usage of register contents and the existence of structurally noneffective code (introns) which are two main differences of this genetic representation from the more common tree-based genetic programming (TGP) variant.[2][3] [4]

Like other Genetic Programming methods, Linear genetic programming requires the input of data to run the program population on. Then, the output of the program (its behaviour) is judged against some target behaviour, using a fitness function. However, LGP is generally more efficient than tree genetic programming due to its two main differences mentioned above: Intermediate results (stored in registers) can be reused and a simple intron removal algorithm exists[1] that can be executed to remove all non-effective code prior to programs being run on the intended data. These two differences often result in compact solutions and substantial computational savings compared to the highly constrained data flow in trees and the common method of executing all tree nodes in TGP. Furthermore, LGP naturally has multiple outputs by defining multiple output registers and easily cooperates with control flow operations.

Linear genetic programming has been applied in many domains, including system modeling and system control with considerable success.[5][6][7][8]

Linear genetic programming should not be confused with linear tree programs in tree genetic programming, program composed of a variable number of unary functions and a single terminal. Note that linear tree GP differs from bit string genetic algorithms since a population may contain programs of different lengths and there may be more than two types of functions or more than two types of terminals.[9]

Examples of LGP programs

Because LGP programs are basically represented by a linear sequence of instructions, they are simpler to read and to operate on than their tree-based counterparts. For example, a simple program written to solve a Boolean function problem with 3 inputs (in R1, R2, R3) and one output (in R0), could read like this: 

R4 = R2 AND R3
R0 = R1 OR R4
R0 = R3 AND R0
R4 = R2 AND R4   # This is a non-effective instruction
R0 = R0 OR R2

R1, R2, R3 have to be declared as input (read-only) registers, while R0 and R4 are declared as calculation (read-write) registers. This program is very simple, having just 5 instructions. But mutation and crossover operators could work to increase the length of the program, as well as the content of each of its instructions.

Note that one instruction is non-effective or an intron (marked), since it does not impact the output register R0. Recognition of those instructions is the basis for the intron removal algorithm which is used analyze code prior to execution. Technically, this happens by copying an individual and then run the intron removal once. The copy with removed introns is then executed as many times as dictated by the number of training cases. Notably, the original individual is left intact, so as to continue participating in the evolutionary process. It is only the copy that is executed that is compressed by removing these "structural" introns.

Another simple program, this one written in the LGP language Slash/A looks like a series of instructions separated by a slash: 

input/   # gets an input from user and saves it to register F
0/       # sets register I = 0
save/    # saves content of F into data vector D[I] (i.e. D[0] := F)
input/   # gets another input, saves to F
add/     # adds to F current data pointed to by I (i.e. F := F + D[0])
output/. # outputs result from F

By representing such code in bytecode format, i.e. as an array of bytes each representing a different instruction, one can make mutation operations simply by changing an element of such an array.

See also

Notes

  1. ↑ 1.0 1.1 M. Brameier, W. Banzhaf, "Linear Genetic Programming", Springer, New York, 2007
  2. ↑ Brameier, M.: "On linear genetic programming ", Dortmund, 2003
  3. ↑ W. Banzhaf, P. Nordin, R. Keller, F. Francone, Genetic Programming - An Introduction, Morgan Kaufmann, Heidelberg/San Francisco, 1998
  4. ↑ Poli, R.; Langdon, W. B.; McPhee, N. F. (2008). A Field Guide to Genetic Programming. Lulu.com, freely available from the internet. ISBN 978-1-4092-0073-4. https://archive.org/details/AFieldGuideToGeneticProgramming. 
  5. ↑ M. Brameier, W. Banzhaf, A Comparison of Linear Genetic Programming and Neural Networks in Medical Data Mining", IEEE Transactions on Evolutionary Computation, 5 (2001) 17-26
  6. ↑ A. Guven, Linear genetic programming for time-series modelling of daily flow rate, J. Earth Systems Science, 118 (2009) 137-146
  7. ↑ R. Li, B.R. Noack, L. Cordier, J. Boree, F. Harambat, Drag reduction of a car model by linear genetic programming control, Experiments in Fluids, 58 (2017) 103
  8. ↑ P.-Y. Passagia, A. Quansah, N. Mazellier, G.Y. Cornejo Maceda, A. Kourta, Real-time feedback stall control of an airfoil at large Reynolds numbers using linear genetic programming, Physics of Fluids, 34 (2022) 045108
  9. ↑ Foundations of Genetic Programming.
  • Slash/A A programming language and C++ library specifically designed for linear GP
  • DigitalBiology.NET Vertical search engine for GA/GP resources
  • Discipulus Genetic-Programming Software
  • MicroGP Genetic-Programming Software (open source)
  • [1] An open-source Linear GP project based on a Java-based Evolutionary Computation Research System (ECJ).
  • [2]



Retrieved from "https://handwiki.org/wiki/index.php?title=Linear_genetic_programming&oldid=4350317"