C++의 유전 알고리즘을위한 최상의 데이터 구조?

Question

내 문제 (대학 프로젝트)에 맞게 조정 된 유전 알고리즘을 구현해야하며 첫 번째 버전은 짧은 매트릭스 (염색체 x 크기의 비트)로 코딩해야합니다.

"0"과 "1"값만 사용한다고해서 잘못된 디자인이었습니다 ...하지만 프로토 타입 일 뿐이므로 의도 한대로 작동했습니다. 이제는 나를위한 시간입니다. 새롭고 향상된 버전을 개발할 수 있습니다. 여기서는 성능이 중요하지만 단순성 또한 높이 평가됩니다.

나는 주위에 연구와 함께했다 : 염색체에 대한

: - 벡터 (벡터 부울에 최적화 된 것으로 보인다) - - 부울 의 배열 - ("0100100010"와 같은) String 클래스 비트 세트

을 (가장 자연스러운 하나의 소리)과 인구 : - C 배열 [] - 나는 C의 벡터를 선택하는 경향이다 큐

- 벡터 hromossome 및 팝업에 대한 배열,하지만 주제에 대한 경험을 가진 사람의 의견을 싶습니다.

미리 감사드립니다.

Answer 1

인구와 유전자에 대한 임의 접근을 원한다고 생각합니다. 성능이 중요하다고 말하면 실행 속도로 해석합니다. 염색체는 vector<>이고 유전자는 vector<char>입니다. vector<char>의 이유는 bitset<>과 vector<bool>이 메모리 소비에 최적화되어 있기 때문에 느립니다. vector<char>은 x8 메모리를 사용하여 더 빠른 속도를 제공합니다 (시스템에서 char = byte로 가정). 속도를 원한다면 vector<char>으로 가십시오. 메모리 소비가 가장 중요한 경우 vector<bool> 또는 bitset<>을 사용하십시오. bitset<>은 자연 선택으로 보일 것입니다. 그러나 비트 수에 따라 템플리트 화됩니다. 즉, a) 유전자 수는 컴파일 시간에 고정되고 알려 져야합니다 (이것은 큰 숫자는 아닙니다 -no) 및 b) 다른 크기를 사용하면 bitset 크기의 코드 당 하나의 사본으로 끝나기 때문에 (인라이닝이이를 부정 할 수는 있지만) 코드가 부 풀리게됩니다. 전반적으로, vector<char>을 원하지 않으면 vector<bool>이 더 나을 것이라고 생각합니다.

vector<char>의 미학을 염두에 둔다면 typedef char gene; 일 수 있고 더 자연스럽게 보이는 vector<gene>을 사용할 수 있습니다.

string은 vector<char>과 비슷하지만 좀 더 성가신 사람입니다.

Answer 2

특히 귀하의 질문에 대답하십시오. 나는 당신이 무엇을 제안하는지 정확히 모르겠습니다. 배열과 문자열 클래스에 대해 이야기합니다. 당신은 큐, bitset, 벡터, 링크 된리스트 등등을 가질 수있는 STL 컨테이너 클래스에 대해 이야기하고 있습니까? 당신이 모집단을위한 벡터 (C 배열에 가장 가까운 것)와 염색체에 대한 비트 세트를 제안합니다. 기억력에 대해 걱정했다. 당신이 이미 당신의 DNA 문자열 표현의 벡터를 사용하고 있다면. ("10110110")

도발적인 아이디어와 좋은 도구. 이 라이브러리를 다운로드하고 처음 사용할 것을 권장합니다. 주요 컴파일러와 함께 작동합니다. 유닉스 변종에서 작동합니다. 모든 소스 코드가 있습니다.

모든 프레임 워크는 당신을 위해 이루어지며 많은 것을 배울 것입니다. 나중에 자신 만의 코드를 처음부터 작성하거나이 클래스에서 상속 할 수 있습니다. 원한다면 상용 코드로도 사용할 수 있습니다.

그들은 당신이 비트 배열에 나무로 구조에 실수로 정수에서 쉽게 DNA의 representaion을 변경할 수 있습니다 객체이기 때문에 등 등

이 참여 항상 학습 치료는하지만, 그것이 가치가있다.

나는 이것을 수천 개의 신경망을 생성하는 데 사용하고 간단한 체력 기능으로 그들을 잡초로 제거하여 실제를 실행합니다.

갈 리브

http://lancet.mit.edu/ga/

Answer 3

당신이 자신을 (외부 라이브러리 kingchris를 원하는 경우가 좋은 일을 갖고있는 것 같아요) 정말 당신이 할 필요가 조작의 종류에 따라 원하는 코드를 가정하면 . 메모리 측면에서 가장 많은 돈을 벌기 위해 정수형을 사용하고 비트 마스크 등을 통해 개별 비트를 설정/조작 할 수 있습니다. 이제이 접근법은 사용의 용이성 측면에서 최적이 아닐 수 있습니다 ... 위의 문자열 예제가 작동합니다 이제 다시 반바지와 크게 다르지는 않지만, 이제는 16 비트 값과 반대로 8 비트 값으로 '0'또는 '1'을 나타냅니다. 또한, 조작에 따라 문자열 케이스가 보이지 않을 수도 있습니다.알고리즘에 대한 정보를 좀 더 줄 수 있다면 더 많은 피드백을 줄 수 있습니다. 나 자신은 정수 (비트 세트)의 일부로 개별 비트를 좋아하지만, 가면, 교대 및 모든 좋은 물건에 익숙하지 않은 경우 귀하에게 적합하지 않을 수 있습니다.

Answer 4

모든 구성원의 관련 기능을 실제 데이터로 멋지게 포장 할 수 있기 때문에 모든 구성원을위한 클래스를 작성하는 것이 좋습니다.

"bool 배열"이 필요한 경우 염색체 수에 따라 int 또는 여러 int (마스크 및 비트 현명한 연산을 사용하여 각 비트에 액세스 (수정/뒤집기))를 사용하는 것이 좋습니다.

인구 집단의 배열은 인구 집단에 단순히 추가 할 수 없기 때문에 일반적으로 인구 집단을위한 일종의 컬렉션 클래스를 사용했습니다. 동적 목록의 일종을 구현하는 것이 좋습니다 (ArrayList에 익숙하다면 좋은 예입니다).

나는 위의 방법으로 유전 알고리즘에 큰 성공을 거뒀습니다. 멤버 클래스를 적절하게 준비한다면 실제로는 단순화 할 수 있고 데이터 구조에 대한 걱정 대신 더 나은 유전 알고리즘을 코딩하는 데 주력 할 수 있습니다.