유전자 프로그래밍을 방해하는 것은 무엇입니까?

유전자 프로그래밍을 방해하는 것은 무엇입니까?

---

나는 유전자 알고리즘에 대한 상당한 양의 작업을 성공적으로 수행했으며 지금까지 유전자 프로그래밍을 무시했습니다. 내가 아는 한, 대부분의 프로그램은 프로그래머가 작성한 것으로 남아 있으며 유전 프로그래밍을 방해하는 것이 무엇인지 궁금합니다.

내가 생각한 몇 가지 가능한 설명은 다음과 같습니다.

1. 검색 공간이 너무 커서 소음 중에서 유용한 프로그램을 찾을 수 없습니다.
2. 대부분의 실제 응용 프로그램은 그러한 공간의 적합성 평가를 허용하기에 충분한 데이터를 제공 할 수 없습니다.
3. 많은 실제 응용 프로그램의 효율성을 단일 피트니스 측정으로 줄이는 것은 어렵습니다. 즉, 적절한 피트니스 함수를 작성하는 것은 실제 프로그램을 작성하는 것과 동일한 양의 작업을 수반 할 것입니다.

어떤 아이디어?

---

이것은 제 자신의 연구에서 고려해 온 것입니다. 여러 가지 이유가 있습니다.

1. GP 분야의 대부분의 연구는 대부분의 프로그래머가 생산하는 일종의 소프트웨어보다는 공식을 생산하는 데 초점을 맞추 었습니다. 이 분야에는 많은 컴퓨터 과학자가 있지만 예상 할 수있는 종류의 프로그램을 제작하는 데 집중하는 사람은 거의 없기 때문에 해당 분야의 발전 속도가 느려졌습니다.

2. 조작하기 쉬운 멋진 트리 구조를 생성 할 수 있고 일부 까다로운 문제를 해결하기 때문에 안타깝게도 명령형 프로그램이 무시 되었기 때문에 LISP를 사용하는 것이 지나치게 강조됩니다. 프로그래머가 GP를 진지하게 받아들이려면 명령형 프로그램을 만들어야합니다.

3. 실제 프로그램에는 루핑 구조가 포함되어 있지만 루프는 무한 루핑을 방지하기위한 모든 종류의 추악한 제약없이 GP에서 구현하기가 어렵습니다.

4. 유전 프로그래밍은 잘 확장되지 않습니다. 사용 가능한 언어가 적은 작은 문제에는 문제가 없지만 첫 번째 요점에서 말했듯이 검색 공간이 너무 빨리 커집니다.

5. 인간 프로그래머에 비해 GP는 매우 느릴 수 있습니다. 그러나 병렬화가 가능하므로 더 많은 수의 프로세서 코어가 표준이됨에 따라 상당한 이점을 얻을 수 있습니다.

또 다른 유효한 대답은 코드가 자동으로 생성되어 신뢰하기 어렵다는 것입니다. 이것은 사실이지만 실제로는 GP가 처음에 올바른 종류의 프로그램을 생산할 수 없기 때문에 이것이 큰 영향을 미치지 않을 것이라고 생각합니다.

---

유전자 프로그래밍의 어려운 부분은 좋은 점수 함수를 작성하는 것입니다.

• 스코어링 기능은 알고리즘에 원하는 속성이 있는지 여부를 올바르게 판단해야합니다. 이것은 소리보다 어렵습니다-테스트 스위트를 작성하는 것보다 훨씬 어렵습니다. 알고리즘은 스코어링 기능의 모든 특성에 적응 하고 최적화 할 수 있습니다. 진화하려고 strcmp? 알고리즘은 대신 합격 / 불합격 테스트 케이스의 길이에 대한 수학적 패턴을 발견 할 수 있습니다.

• 스코어링 기능은 테스트중인 알고리즘이 부분적으로 작동하는지 여부를 판단 할 수 있어야합니다. 유전 적 프로그래밍은 "언덕 등반"에 의존합니다. 작은 유익한 돌연변이는 점수를 조금씩 점진적으로 개선해야합니다. 점수 매기기 기능이 참 / 거짓 만 출력 할 수 있다면 유 전적으로가 아니라 무작위로 검색하는 것입니다.

손을 뻗어 보면 유전 프로그래밍이 측면 사고의 궁극이라는 것을 알게 될 것입니다. 당신의 프로그램은 당신이 생각하지 못했던 모든 방식으로 문제를 해결하는 경향이있을 것입니다. 쓸모없는. 한 가지 유명한 사례는 기본적인 전자 부품을 사용하여 발진기를 발전시키려는 시도였습니다. 회로의 단순성과 출력 발진 여부를 판단했다. 연구자들은 그것이 작동하지 않는다고 확신하는 아주 단순한 것을 만들어 냈지만, 그것은 환경으로부터 전파를 포착하고 증폭시키는 것이었다.

인용 편집 :

Graham-Rowe, Duncan. "전자 수프에서 라디오가 나온다." New Scientist, vol.175, no.2358, p.19 (2002 년 8 월 31 일). http://www.newscientist.com/news/news.jsp?id=ns99992732 에서 온라인으로 사용 가능

그러나 이제 링크가 끊어진 것처럼 보입니다.

새 링크는 http://www.newscientist.com/article/dn2732-radio-emerges-from-the-electronic-soup.html 입니다 .

---

이 파티에 늦었다는 건 알지만 몇 가지 요점을 말씀 드리고 싶습니다. 나는 그의 Genetic Programming 4 책에서 John Koza와 함께 일할 수있는 엄청난 행운을 가졌습니다.

GUI 이벤트 연결, 픽셀 푸시, 데이터베이스 등 우리 대부분이 매일하는 프로그래밍 은 GP가 구축하려는 프로그램 유형이 아닙니다 .

John Koza가 약 백 대의 컴퓨터 클러스터로 수행하는 작업은 (내가 기억한다면!) 흥미로운 문제에 대한 해결책을 찾는 것입니다 (NP-hard를 생각해보십시오). 슬프지만 우리 프로그래머가 매일 일하는 대부분의 문제는 그다지 흥미 롭거나 어려운 문제가 아니며 대부분 짜증나고 시간 소모적입니다.

Ben Jackson이 유전 공학 전자 발진기에 대해 말한 것은이 스레드에서 Koza 박사와 팀이 실제로하는 일과 가장 가까운 것입니다. GP 시리즈 책에는 회로의 많은 예가 있습니다.

Tom Castle이 여기서 명령형 프로그램에 대해 말한 것은 정확히 사실이 아닙니다. John과 회사의 중요한 예는 안테나 설계 실행입니다. 안테나를 디자인하는 LOGO 드로잉 언어와 같은 명령을 사용하는 거의 3D 드로잉 프로그램입니다. 스택에서 행렬을 푸시하고 팝하기위한 moveto, lineto 유형 명령이 있습니다. 지난주에 살펴본 GP 패키지 인 jgap은 직접 지원합니다. void return 문을 포함 할 수 있고 끝에 return 문이있는 컨테이너 유형 비 터미널입니다. 너무 자세히 보지 않았지만 지역 변수와 같은 것이 있다고 생각합니다.

초기 GP가 중심으로 실행되는 원래 LISP 디자인은 때때로 고통 스럽습니다. 확실히 사실입니다. GP 실행의 출력을 더 사용 가능한 코드로 변환하는 것에 대해 짜증나는 것으로 생각하는 통과 의례입니다.

요약 : GP는 실제로 자동 프로그래밍 시스템이 아닙니다. 자동화 된 발명 시스템입니다.

---

나는 1과 3이라고 말할 것입니다.

특히, 점 3와 직결 된 나는 대부분의 경우는 심지어 말을 쉽게 적절한 대상 기능을 마련하는 것보다 실제 프로그램을 작성 하고 올바른 또는 수용 가능한 해결책이 리드 (방법이 있음을 알고 있는지 확인 유전자 프로그래밍에서 파생 된 알고리즘이 예상대로 작동합니까?)

포인트 1과 관련하여 검색 공간에는 무한한 수의 차원이 있다고 말할 수 있습니다.

---

세개:

1. 로 앙드레 말한다 , 충분하다 피트니스 함수를 작성하는 것은 매우 어렵다. 이것은 Test Driven Development의 궁극적 인 버전입니다. 아직 작성되지 않은 프로그램의 100 % 적용 범위를 제공하는 단위 테스트를 작성해야합니다. 그럼에도 불구하고 100 % 커버리지만으로는 충분하지 않을 것입니다. 복잡한 시스템의 모든 측면의 정확한 동작을 공식적으로 지정하고 주어진 프로그램이 해당 사양을 충족하는지 확인하는 문제를 해결하면 기회가있을 수 있습니다.
2. 유전 프로그래밍은 비 결정적이며 정확한 솔루션보다는 근사 솔루션을 생성하는 데 더 적합합니다.
3. 합리적으로 복잡한 문제에 유전 프로그래밍을 적용하면 계산 비용이 많이 듭니다. 1999 년에 Genetic Programming Inc는 현장 작업에 1,000 노드 클러스터 를 사용했습니다.

---

GP는 피트니스 기능을 만드는 사람이 알 수없는 새로운 문제를 빠르게 해결할 수 없습니다. 따라서 현재는 우리가 이미 해결 방법을 알고있는 문제를 해결하는 데만 사용할 수 있지만 검색 공간으로 인해 완전히 해결하기에는 이상적이지 않습니다. 여행하는 세일즈맨과 같은. GA로 더 빨리 해결할 수 있습니다.

그 이유는 실제로 매우 간단합니다. 새로운 문제를 해결하기 위해 GP에게 제공하는 도구는 GP 검색 공간이 실제 유전학에 대한 진정한 아날로그가 될만큼 충분히 간단하거나 완벽해야합니다.

실제 유전학과 마찬가지로 유전 프로그래밍은 모든 플랫폼 성장 시스템과 동일한 성장 패턴을 따릅니다. 즉, GP는 포함 된 핵심 유틸리티가 플랫폼에 도달하는 지점까지 진행되고 수평을 맞춘 다음 새로운 플랫폼을 구축하기 위해 새로운 패러다임에 발을 들여 놓기까지 오랜 시간이 걸립니다.

이 진보적 인 비디오는 이러한 플랫폼 성장 패턴을 보여줍니다. http://www.youtube.com/watch?v=mcAq9bmCeR0 새 핸드를 개발하는 데 시간이 오래 걸리고, 일단 추가 핸드가 새로운 것이되고 더 많은 핸드의 최적의 예로 빠르게 진행됩니다. (이 비디오는 GP가 아닌 GA를 사용할 가능성이 가장 높지만 유전학은 유전학입니다)

이것은 모두 특이점 이론 (BTW)에 들어가는 것과 동일한 논리입니다.

But what this means for GP is that it pretty-much is only good for research, not for practical application within a program. With a few simple exceptions where the requirements are slightly more in-depth than a GA can solve. Such as some scheduler programs. Where the programming search space is pretty small, and where the tools needed to solve it are well understood, and where there can be a well-defined fitness function.

---

It's simply because it has been proven to be theoretically impossible (at least for correct programs).

Let's assume you have an infinite computing power discarding search space size and slowness issues and other 'speed' stuff. Now you face only two problems : - Will the generated program stops ? - How to be sure that the generated program behave the way I want them to ?

The first problem is a central question in computability theory and is called the halting problem . Turing proved in 1936 that this problem is undecidable for all program-input pairs. This means it is possible in some cases, but not for all. There is no automated process that can determine wether a program halts or not. So for this, you can't do much ;)

The second issue related to program correctness. In genetic programming, validation is usually made through example values which does not constitute at all any proof of correctness. This is comparable to unit testing, gives ok for a number of examples, but not no general proof. For example if I write a prime number checker, test it only with 3 5 7 and 11, then a program that returns true for every odd number would pass the test.

Going one step further would be to use automated proofs. Automated proof of correctness for algorithms is in fact deeply related to mathematical automated theorem proving. You describe your program using an axiomatized system and try to automatically proof the correctness of your statement. Here again you face strong theoretical barriers, which are the Gödel Incompleteness theorems. These theorems state among others things that for even very simple axiomatized systems, able to perform arithmetic on natural numbers, there is no algorithm (called effective procedure) able to proof all the theorems regarding these natural numbers. Concretely, this means that even for simple programs, you will not be able to prove its correctness.

Even without a proven correctness, using sample test cases to validate the genetic program is very prone to over-specialization, the phenomenon known as overfitting in machine learning. That is, the learnt program will do fine on the provided test cases but may go totally ballistic for some other inputs.

---

Maybe that most programmers are programmers, and not computer scientists?

Genetic programming requires serious smarts. You need to be able to break the problem down appropriately, and you need an appropriate problem to start with. And you need to know enough to know that genetic algorithms are an option. And the problem needs to not already have a well known solution.

Not everything needs a fancy algorithm. Of all the code that is written in the world, do 'standard' webapps, OSs, device programming, really need genetic algorithms?

And when it comes down to it, most programming effort is devoted to solving simple problems where a complicated approach is not needed.

---

I think a big part of the reason is risk management. Bear with me: when a programmer sits down to write a program, they have at least some idea of how long it'll take and of what they can do.

When instead a programmer sits down to write a program that will generate a program (using genetic programming), the uncertainty shoots through the roof: it's unclear how long the process will take, and it's unclear how good the end program can be.

There is also uncertainty in other places: how easy will it be to adjust the program later, or to fix bugs? Generated code can be nigh-impossible to debug.

---

Primordial soup is suspicious and unappetizing. For my production code I prefer Intelligent Design.

---

My personal view after couple years in GP research at university and following the field afterwards: GP fails to scale.

Simple problems represented by simple fitness functions GP can solve all right. But as mentioned before - formulating a fitness function that describes the task of evolving strcmp or a calculator or even a simple text editor is almost impossible using classic approaches.

I do like the notion of GP fitness function being TDD in perfection, though :-) Maybe some bright mind will come up with a better way of directing the simulated evolution some day but that has yet to happen..

I have some hopes for GP in the area of implicit fitness functions where I'm currently doing some 'private research'. We'll see how far it'll get!

Cheers, Jay

---

There are some projects tackling the above mentioned problems in GP. An example would be the opencog MOSES

---

Nowadays programming is defining the fine specification in a machine readable way. You tell the programm what exactly you want it to do and how the result should look like. Its not much more anymore. That means if you want to generate the result by e.g. genetic programming you still have to do this machine readable fine specification in form of a fitness function. This would lead to at least the same but probably bigger amount of work. So its just the wrong field for genetic programming which is made for problems with an easy to define but a hard to reach specification.

edit: you could now say that in most projects this fine specification is done anyway in form of tests. i would say for a genetic programming approach tests are way to imprecise to specify you're needs. They are example based and not like programming based on a formal specification language. Genetic programming would probably produce results that suit the test cases and behave wrong in real situations with new inputs. So to get a specification level with tests thats as exact as a specification with a programming language you would need a huge amount of test cases for every eventuality. So finally you would end up in doing much more work than programming that stuff.

---

GP and GA, or in general Evolutionary Algorithms are more like hobbies. They are not used for real-life application, barring exceptions. The reason is that these algorithms are based on randomness. There is no certainty of getting a good answer.

Moreover, this area is flooded with sub-par research work, because its easy to understand and implement compared to other mathematically intense techniques. So students just find an objective to optimize in some engineering or science application and you have a new work - to get published.

Just compare the sponsors for their conferences with those of other AI/ML/Optimization conferences. It will be clear about their "current" importance in industry.

But its an area of research, and its upto us to make it work. At present its just a hobby!

참고URL : https://stackoverflow.com/questions/4380627/what-is-holding-genetic-programming-back