모델링 : 효율적으로 하위 집합 선택 모델

Question

Optaplanner를 사용하여 모델링하고 해결하려는 문제는 스포츠 팀 (여기 : 축구)의 명단을 만드는 문제입니다. 즉 : 사용 가능한 모든 플레이어 중에서 몇 가지 기준에 따라 11을 선택하십시오. 유효한 솔루션을 정의하기 위해 하드/중간/소프트 점수를 사용하고 있습니다. 정확히 한 명의 골키퍼가 명단에 나와 있어야한다는 엄격한 기준. 플레이어가 선택된 순서는 중요하지 않습니다.

나는 현재 내 PlanningEntity로 이것을 가지고 : 만 getMembers 사용하는 점수 계산에

@PlanningEntity 
public class Roster 
{ 
    @PlanningVariable(valueRangeProviderRefs = {"candidates"}) 
    private RosterMember member1; 
    @PlanningVariable(valueRangeProviderRefs = {"candidates"}) 
    private RosterMember member2; 
    @PlanningVariable(valueRangeProviderRefs = {"candidates"}) 
    private RosterMember member3; 
    @PlanningVariable(valueRangeProviderRefs = {"candidates"}) 
    private RosterMember member4; 
    @PlanningVariable(valueRangeProviderRefs = {"candidates"}) 
    private RosterMember member5; 
    @PlanningVariable(valueRangeProviderRefs = {"candidates"}) 
    private RosterMember member6; 
    @PlanningVariable(valueRangeProviderRefs = {"candidates"}) 
    private RosterMember member7; 
    @PlanningVariable(valueRangeProviderRefs = {"candidates"}) 
    private RosterMember member8; 
    @PlanningVariable(valueRangeProviderRefs = {"candidates"}) 
    private RosterMember member9; 
    @PlanningVariable(valueRangeProviderRefs = {"candidates"}) 
    private RosterMember member10; 
    @PlanningVariable(valueRangeProviderRefs = {"candidates"}) 
    private RosterMember member11; 

    public List<RosterMember> getMembers() 
    { 
     return Lists.newArrayList(member1, member2, member3, member4, member5, member6, member7, member8, member9, member10, member11); 
    } 
} 

, 즉 플레이어가 member1 또는 member2에 할당되어있는 경우 난 상관 없어. 솔버는 대부분 기본 구성을 사용하며 100 초 후에 시간 초과되거나 10 초 후에 개선되지 않으면 구성됩니다.

일부 샘플 데이터 세트에서이 문제를 해결 한 후에는 대부분의 경우 최적의 솔루션을 찾지 못했지만 (적어도 유효 함) 알아 냈습니다. 최고의 골키퍼가 선택되지는 않습니다. (많은 수의 골키퍼가 없기 때문에 골키퍼를 선택해야합니다.)

나는 이것이 내가 모델화 한 방법과 관련이 있다고 생각한다. 모든 명단 멤버를 separetely로 설정할 수 있기 때문에 이것은 솔루션 공간을 불필요하게 크게 만드는 것처럼 보인다. 앞서 언급했듯이 멤버가 할당 된 필드는 중요하지 않습니다. 배정 된 사람과 그렇지 않은 사람이 중요합니다. 따라서 기본적으로 일부 제약 조건과 최적화 기준을 충족하면서 플레이어의 하위 집합을 선택해야합니다.

단순히 List of RosterMember을 @PlanningVariable으로 주석 달기는 작동하지 않는 것 같습니다. 나는 또한 예에서도 비슷한 상황을 발견 할 수 없었다. 이것이 단순한 모델링 예일 것입니다.

내가 지금까지 생각해 낼 수있는 유일한 아이디어는 명시 적으로 (하드) 제약 조건 중 일부를 모델링하는 것입니다. 범위를 계획 변수 중 하나에 대해 goalkeeper으로 제한하고 다른 모든 값은 non-goalkeeper (또는 그 이상)으로 제한합니다. 문서 (4.3.5.2.3.)에 따르면 이는 피하는 것이 좋습니다.

편집 : 나는 하나의 명단 인스턴스 만 가지고 있습니다. 서로 다른 팀의 명단은 서로 관련이 없으며 각 팀의 해결사를 순차적으로 실행하려고 계획하고 있다고 가정합니다.

편집 2 : 제안에 따라, 나는 지금 대신 이전 Roster이 있습니다

@PlanningEntity 
public class RosterAssignment 
{ 
    @PlanningVariable(valueRangeProviderRefs = {"candidates"}) 
    private RosterMember member; 
} 

초기 미해결 솔루션을 만드는, 내가 열한 빈 RosterAssignments를 추가합니다. 각 Day 예를 들어, 4 개 TeamAssignment 인스턴스가 아닌 4 개 계획 변수가 :

(DefaultConstructionHeuristicPhase.java:158) Construction Heuristic phase (0) ended: step total (11), time spent (111), best score (-1hard/-2medium/1275soft). 
(DefaultLocalSearchPhase.java:152) Local Search phase (1) ended: step total (375104), time spent (10111), best score (-1hard/-2medium/1275soft). 
(DefaultSolver.java:238)  Solving ended: time spent (10129), best score (-1hard/-2medium/1275soft), average calculate count per second (75545), environment mode (REPRODUCIBLE). 

Answer 1

테니스의 예를 참조하십시오 : 시작 솔루션을 만든 후 해결사 아무것도 개선 할 수있을 것 같지 않습니다 그러나 Day 그 자체.

검색 공간은 동일하지만 TeamAssignment "day1-spot1"과 TeamAssignment "day2-spot3"을 바꿀 수 있으므로 기본 이동 (changeMove 및 swapMove)이 훨씬 잘 작동합니다.