C ++의 유전자 알고리즘에 대한 최상의 데이터 구조?

Question

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

짧게 선언했지만 "0"및 "1"값 만 사용하기 때문에 나쁜 디자인이었습니다. 그러나 그것은 단지 프로토 타입이었고 의도 한대로 작동했으며 이제는 새로운 것을 개발할 때입니다 , 개선 된 버전. 여기서는 성능이 중요하지만 단순성도 높이 평가됩니다.

나는 주변에서 연구하고 다음과 같이 생각했다.

염색체의 경우 : - 문자열 클래스 (예 : "0100100010") - BOOL 배열 - 벡터 (벡터는 bool에 최적화 된 것으로 보임) - 비트 세트 (가장 자연스러운 소리)

그리고 모집단 : -C 배열 [] - 벡터 - 큐

나는 염색체를 위해 벡터를 선택하고 팝을위한 배열을 선택하는 경향이 있지만, 주제에 대한 경험이있는 사람의 의견을 원합니다.

미리 감사드립니다!

Answer 1

나는 당신이 인구와 유전자에 무작위로 접근하고 싶다고 생각합니다. 당신은 성능이 중요하다고 말하면서 실행 속도로 해석합니다. 그래서 당신은 아마도 a를 사용하는 것이 가장 좋습니다 vector<> 염색체 및 a vector<char> 유전자를 위해. 대한 이유 vector<char> 그게 다 bitset<> 그리고 vector<bool> 메모리 소비에 최적화되므로 느립니다. vector<char> X8 메모리 비용으로 더 높은 속도를 줄 것입니다 (가정합니다. char = 시스템의 바이트). 따라서 속도를 원한다면 함께 가십시오 vector<char>. 메모리 소비가 가장 중요하다면 사용하십시오 vector<bool> 또는 bitset<>. bitset<> 그러나 여기서 자연스럽게 선택한 것처럼 보일 것입니다. 비트의 수에 템플릿이 템플릿으로 표시되어 있음을 명심하십시오. 이는 a) 유전자의 수가 고정되어 컴파일 시간에 알려져야한다는 것을 의미합니다. 아니오) 및 b) 다른 크기를 사용하는 경우, 당신은 하나의 사본으로 끝납니다. bitset 각각의 크기 bitset 사용하는 방법 (인라인이이를 무효화 할 수 있지만), 즉 코드 블로트. 전반적으로, 나는 추측 할 것이다 vector<bool> 원하지 않는다면 더 좋습니다 vector<char>.

미학에 대해 걱정한다면 vector<char> 당신은 할 수 있습니다 typedef char gene; 그리고 사용하십시오 vector<gene>, 더 자연스럽게 보입니다.

ㅏ string 똑같습니다 vector<char> 그러나 더 번거 롭습니다.

Answer 2

구체적으로 귀하의 질문에 답하십시오. 나는 당신이 무엇을 제안하는지 정확히 잘 모르겠습니다. 배열 및 문자열 클래스에 대해 이야기합니다. 큐, 비트 세트, 벡터, 링크 목록 등을 가질 수있는 STL 컨테이너 클래스에 대해 이야기하고 있습니까? 메모리 용량에 대해 걱정합니다. 그렇지 않으면 이미 DNA의 문자열 표현 벡터를 사용하고 있습니다. ( "10110110")

아이디어와 뒤틀리는 좋은 도구. 이 라이브러리를 다운로드하고 처음 사용하는 것이 좋습니다. 주요 컴파일러와 함께 작동합니다. UNIX 변형에서 작동합니다. 모든 소스 코드가 있습니다.

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

그것들은 대상이기 때문에 정수에서 실제로, 구조, 나무, 비트 어레이 등의 DNA의 표현을 쉽게 변경할 수 있습니다.

항상 학습 치료법이 포함되어 있지만 그만한 가치가 있습니다.

나는 그것을 사용하여 수천 개의 신경망을 생성 한 다음 간단한 피트니스 기능으로 잡초를 제거한 다음 실행합니다.

갈리브

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

Answer 3

당신이 이것을 직접 코딩하고 싶다고 가정하면 (외부 도서관을 원한다면 Kingchris가 좋은 것을 가지고있는 것 같습니다) 실제로 어떤 종류의 조작이 필요한지에 달려 있습니다. 메모리 측면에서 벅에 대한 최대한 강타를 얻으려면 정수 유형을 사용하고 비트 마스크 등을 통해 개별 비트를 설정/조작 할 수 있습니다. 이제이 접근법은 사용 편의성 측면에서 최적이 아닐 수 있습니다 ... 위의 문자열 예제는 작동합니다. 그러나 다시 한 번 반바지와 크게 다르지 않습니다. 여기에서는 이제 16 비트 값과 달리 8 비트 값으로 '0'또는 '1'을 나타냅니다. 또한 다시 조작에 따라 문자열 케이스는 아마도 다루지 않을 것입니다. 따라서 알고리즘에 대해 더 많은 정보를 제공 할 수 있다면 더 많은 피드백을 줄 수 있습니다. 나 자신은 정수 (비트 세트)의 일부로 개별 비트를 좋아하지만, 마스크, 교대, 그리고 모든 좋은 것들에 익숙하지 않은 경우, 그것은 당신에게 맞지 않을 수 있습니다.

Answer 4

나는 모든 인구 구성원에 대한 수업을 작성하는 것이 좋습니다. 모든 회원의 관련 기능을 실제 데이터로 멋지게 포장 한 동일한 장소에 유지할 수 있기 때문에 물건을 상당히 단순화하는 것이 좋습니다.

"Bols 배열"이 필요한 경우 INT 또는 여러 Ints를 사용하여 염색체 수에 따라 마스크 및 비트 현명한 작업을 사용하여 각 비트에 액세스 (수정 / 플립)를 사용하는 것이 좋습니다.

나는 보통 인구를 위해 일종의 컬렉션 클래스를 사용했습니다. 왜냐하면 많은 인구 구성원만으로도 단순히 인구를 더할 수 없기 때문입니다. 나는 일종의 동적 목록을 구현하는 것이 좋습니다 (Arraylist에 익숙하다면 좋은 예입니다).

나는 위의 레시피가있는 유전자 알고리즘으로 큰 성공을 거두었습니다. 회원 수업을 올바르게 준비하면 실제로는 단순화 될 수 있으며 데이터 구조에 대해 걱정하는 대신 더 나은 유전자 알고리즘을 코딩하는 데 집중할 수 있습니다.