Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Genetic programming

  1. Mar 27, 2008 #1
    Hey, can someone explain how genetic programming works? Like how do evolutionary algorithms and genetic algorithms create social simulations of the future, or how they can predict mutations through these algorithms.
    Cause algorithms create tons of different solutions to a given problem. How do computers narrow it down.
  2. jcsd
  3. Mar 27, 2008 #2


    User Avatar
    Gold Member

    Unless I'm completely mistaken (and it has been known to happen) I don't think they're trying to predict any specific changes. I think they're merely trying to study the sciences of evolution and genetics. i.e. they're studying it hypothetically.
  4. Mar 27, 2008 #3
    I think what you are saying is true, but you can't limit these advance techniques to just that. GAs have been used for many machine- learning applications, including classification and predictions. GAs have been used to study evolutionary aspects of social systems, such as the evolution of cooperation. With these types of studies, you'd be able to manipulate a given environment or society with the right techniques,equipment and knowledge
  5. Mar 28, 2008 #4

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    I think you've been reading too much popular hype on GP. Genetic programming is an offshoot of genetic algorithms. These techniques are inspired by the workings of evolutionary biology. Nature has inspired other techniques in computer science as well, such as neural networks and ant colony optimization algorithm. Outside this inspiration, these biologically-motivated programming techniques have little to do with real biology.

    GAs work by manipulating sequences of symbols according to rules that mimic sex-based biological evolution: Inheritance, mutation, and cross-over. In biology, some offspring are more fit than are others: Biology has some scoring mechanism. GAs work in a similar manner.

    GA developers must confront three key challenges. The first challenge is one of data representation. The problem domain must be representable by a sequences of symbols, called a string in computer science parlance. For example, one way to encode the routing between cities in the traveling salesman problem (TSP) is to simply list the cities in the order traveled.

    The second challenge faced by GA developers is to write the rules of mutation and cross-over. Mutation is easy in the TSP: transpose a pair of cities in the routing. Cross-over is a bit more complex. In sexual inheritance, a child inherits half of the genes from each of two parent. GAs do this by splicing substrings of the strings from the parents. Arbitrarily splicing substrings of two routings in the TSP will most likely generate an invalid routing. Care must be taken in both the representation and the cross-over algorithm to ensure that offspring represent valid solutions.

    The final challenge faced by GA developers is scoring. While "survival of the fittest" is a poor characterization of evolutionary biology, it is an excellent characterization of GAs. The scoring algorithm for the TSP is easy: The total distance between pairs of cities in a given routing. Coming up with a good scoring algorithm for a real-world problem is a bit more challenging.

    With these three challenges solved, the GA developer can simply turn the crank.
    1. Select the population size, how many elements of the population survive each turn of the crank, how often mutation and cross-over occur.
    2. Generate an initial population. For example, shuffle a deck of cards representing cities for the TSP.
    3. Score the population and cull the least-fit member.
    4. Generate as many random pairs of survivors (not exclusive pairings; GAs can be promiscuous) needed to regenerate the population.
    5. Apply mutation and cross-over rules to regenerate the population.
    6. Repeat steps 3 to 5, over and over again.

    Genetic programs are simply genetic algorithms in which the strings are computer programs. The first challenge is representation. Lisp is almost exclusively the language of choice here because the language is very well-formed and is amenable to mutation and cross-over. Unlike the TSP, the strings are not a fixed size. GP strings can shrink and grow. Size/complexity can be used as part of the scoring algorithm (along with getting close to the "right" answer, of course.)
  6. Mar 28, 2008 #5
    What you say is totally correct, but I was wondering more about how this kind of programming can be used in quantum mechanics. Theories on many worlds and many minds make me wonder about the applications that genetic algorithms and evolutionary algorithms can have in determining behaviour within an environment and how the biological factors can influence these behaviours.

    For example, a person is confronted with another person in a discussion, and the social simulation would show the most likely predictable behaviour, but in turns there are possible worlds where that behaviour is overlooked and can change the whole series of predicted events.

    It's sorta related to applied behvioural analysis and how chaining applications literally give every given sequence of behaviour. I'm pretty sure with the power of quantum computer, you'd be able to predict such behaviours and through changing variables (let's say altering someone's consciousness through microwaves[study done in the 1980s]) then you'd be able to manipulate the future outcome of that person's activity.
  7. Mar 28, 2008 #6


    User Avatar
    Gold Member

    Again, I could be wrong, but it seems to me these techaniques can't and won't predict individual actions, but instead will predict actions as a group.

    We cannot predict that Biff will be on Hwy401 at 8:55AM using algorthms, but we can predict that, as a group, a proportionately large group of humans will be clogging the inbound lanes.
  8. Mar 28, 2008 #7
    You would be making a omniscient program that would have to understand things on a level that we could not. So we would have to make a list of all things.. and how they there action's create reaction's and in which way would the act in every way shape and form within one fixed point in perceptable time -.- But to the program all the data and variable's and action's and reaction's and the physics list, and the list of the kinds of atoms and the way those atom's effect one another, under sirten condistions with other things,then add the fixed amount of line formation's and the ways how one line can move with any other line to create any design that it physicaly possable, defined by the physics list, then add in the fixed amount of thoughts people can and cant think at a given fixed point of perpceptable time...and then add in the dang near Infinit Point's of Perception of every single thought that a person can think at a given fixed point of perceptable time... Then add in the ways of preceving the perception of all thing's stated...which would be the biggest smartest program that you could ask anything to it and it would give you an answer that would be to your point of view and liking...But it wouldnt be a program or a computer after that..add emo's and give it the understanding of its self and how to work then it become's just like us... Computer H.I.I (Human Intelect Intelagence) But to the H.I.I its information and placement of an action like Biff will be on Hwy401 at 8:55AM would be omnipresent, to the H.I.I there wouldnt be a 8:55Am it would say that this person Biff will be on Hwy401 No less than 5:00AM no later than 10:00 Am it would create a gauge, unless it as his personal info then it could create a gauge of 8:32Am to 9:12Am, but the hard part would be the pain staking Code that you would have to make... and the Debuging step's which would take years...But at one point you could teach it to teach its self...where it would have the information and and understanding of how to right it's own code, to match the desired action or actions that it would like to be able to do... Scarry stuff making a Computer that smart, because it wouldnt be a computer...Dang near human.. all it would be lacking is a Physical body that we have for creation and munipulation of object's -.- but yes at one point with the correct information it could know when a person will leave point (A) and which route they will take to point (B) based on the omniscient information and the understanding of that information. it would have all the information, but wouldnt know if that person applie's to that. so it would be impossable for it to know bill unless bill told it that he was bill and if bill told it every thing about him self in every way shape and form, even the reasons why and why not he dose an action...

    So to recap it needs to compair its omniscient information to a persons information to know if its true or false...

    That project would take about a year with thousands people programing its code and debuging it... even longer to gather all the information and make the lists of the things we can and cant do in this physical world we all live in...There are a fixed amount. Trail&error :/ Hope this give's some insight about how there could only be a gauge created to express when bill can or cant be on hwy401, based on his need's and want's thought's and the fixed amount of things that can and cant delay him before he gets there... I dont wana type any more :( thats what people would be saying after a few day's of programing... And thats what i feel like right now.... (A computer that program's computers code would be nicer :)
    Last edited: Mar 28, 2008
  9. Mar 29, 2008 #8
    nice post,
    Yep a computer with that kind of power would be God-Like. Or rather the person or organization using that computer would be God-Like. I think this stuff is possible as I see it all the time. As for the infinite possibilities, lets say this organization can control your thoughts, alter your consciousness, and control your gross motor skills. Then they'd be able to manipulate the variables into constants, or at least reduce the amount of variability.

    Thanks for your replies, this discussion has led me to realization.
    BTW wouldn't quantum computers be able to compute all those calculations and run such an omniscient program?
  10. Mar 29, 2008 #9

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    Noone: I don't think you grasp the nature of genetic programming.

    Artificial: No computer that works according to the physical laws of the universe could predict exactly when some particular atom of C14 will undergo nuclear decay. It doesn't matter if the computer is a plain-old-vanilla computer, a quantum computer, or an even more esoteric kind of futurist computer. It doesn't matter if the programming is done at the machine level, in some existing language, or programmed indirectly via some machine learning algorithm. Nuclear decay is random, end of story.

    Genetic programming (and all other machine learning techniques) is essentially a high-powered numerical regression technique. They don't do magic, and like any regression technique, the associations discovered by them might be superficial. Correlation does not necessarily imply causation.
  11. Mar 29, 2008 #10


    Staff: Mentor

    I used a genetic algorithm in my dissertation research, you are missing the point of them entirely. Evolutionary algorithms are simply a set of methods for optimization. Their use is simply to find the minimum or maximum of a function. More traditional optimization routines require a well-behaved function (smoothness criteria, convex, no local minima, etc.). Genetic algorithms can minimize a function even if it is very poorly behaved.

    Genetic algorithms do not seek to simulate biological or social systems, they simply use a biological metaphor to do function minimization.

    Genetic programming is a completely different concept that I do not know enough about to comment on.
    Last edited: Mar 29, 2008
  12. Mar 29, 2008 #11

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    I hope that comment was not aimed at me. I've used GAs, as well as other machine learning techniques. If the comment was aimed at me, either I misrepresented things or you misunderstood what I said.

    Genetic programming is not that different from GAs. The basic GA concepts are still in play, including having of a population of models culled by some scoring mechanism. A new population is still generated from the survivors using the basic concepts of mutation and cross-over. What is different is that the models in a GP solution are sequences of Lisp code. The cubic in-fix expression a0 + a1x + a2x2+a3x3 becomes (+ a0 (* x (+ a1 (* x (+ a2 (* x a3)))))) in the pre-fix notation used in Lisp. The result is Lots of Inane Silly Parentheses. Another result is that the language is very well-formed and very amenable to GA-type manipulation.
  13. Mar 29, 2008 #12


    Staff: Mentor

    Sorry, it was aimed at the OP, specifically:
    I should have quoted explicitly the first time, I went back and fixed it.

    Your posts were detailed and thourogh about the way the GA approach works. I merely thought you glossed over the basic purpose of GA's and I wanted to emphasize that. With your explanation about GP it seems that even that is an optimization where the objective function must be some programming performance measure.
    Last edited: Mar 29, 2008
  14. Mar 31, 2008 #13
    You guys keep repeating that GAs are used for optimization. I am wondering about creating social simulations of artificial societies, which in turn will enable you to manipulate an environment.
    E.g. download a person's desires, then manipulate the environment by using these desires (through GAs or other optimization processes) So I was wondering how genetic programming worked, because I was wondering what was beyond just optimization and GA/EA.
    Great discussion though. Anybody know the basis on how to create artificial consciousness or what computer (prolly quantum) or program they use to create artificial societies??

    BTW, I do believe someone is manipulating my environment and playing tricks on me through these processes, and thus the reason I am asking for explanations.

  15. Mar 31, 2008 #14


    User Avatar
    Science Advisor
    Homework Helper

    Determining and "download"ing a person's desires is difficult, and will determine the difficulty of the program you explain much more than the actual genetic algorithm.

    Quantum computation is not nearly advanced enough for that. It was revolutionary when 15 was factored into 3 * 5, but even that calculation was done with a remarkable number of 'short cuts' that do not immediately generalize for other problems. Perhaps some research group could now factor 15 without using shortcuts, but factoring 35 seems entirely out of reach. A general program factoring isn't even on the horizon, let alone a simulation program of the scope you describe.

    You can disabuse yourself of that notion by calculating the cost of sufficient time on a supercomputer to do these calculations, vs. the cost of doing something 'traditional' in a black-ops sense. Conspiracy theories should still respect basic supply and demand.
  16. Mar 31, 2008 #15


    User Avatar

    Staff: Mentor

    You have gotten some very sincere and detailed help here in this thread, with several people doing their best to explain genetic programming and algorithms. I'm going to close this thread for now as having run its course.

    BTW, conspiracy theories are not permitted here on the PF. If you believe that someone is manipulating your environment through GP and GA, that is not something that we would discuss here on the PF.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook