ApproximationControl

근사해를 구하는 로직과 관련된 기능을 담당하는 컨트롤

IsApplyStateFiltering

public override bool IsApplyStateFiltering()

정의

탐색할 State를 필터링할지 여부를 정의합니다. State를 필터링하는 로직은 State Transition을 필터링하는 Local 필터링과 Stage의 State를 대상으로 필터링하는 Global 필터링이 있습니다.

반환

Type	Description	Default
Boolean	State 필터링 로직 적용 여부입니다.	False

예제 (Default Logic)

public override bool IsApplyStateFiltering()
{
    return false;
}

IsApplyApproximation

public override bool IsApplyApproximation()

정의

근사해를 구하는 로직을 적용할 지 여부를 설정합니다.

반환

Type	Description	Default
Boolean	근사해를 구하는 로직 적용 여부입니다.	False

예제 (Default Logic)

public override bool IsApplyApproximation()
{
    return false;
}

IsUseEstimationValue

public override bool IsUseEstimationValue()

정의

State에서 가치 추정값을 계산하고 활용할지 여부를 설정합니다.

반환

Type	Description	Default
Boolean	True: 적용 False: 미적용	False

예제 (Default Logic)

public override bool IsUseEstimationValue()
{
    return false;
}

GetEstimationValueUpdatePeriod

public override int GetEstimationValueUpdatePeriod()

정의

State에서 가치 추정 값을 계산하는 주기를 설정합니다. 즉, 해당 주기가 n일 경우 n번째 State마다 State의 가치 추정 값을 계산합니다.

반환

Type	Description	Default
Integer	State의 가치 추정 값을 계산하는 주기입니다.	1

예제 (Default Logic)

public override int GetEstimationValueUpdatePeriod()
{
    return 1;
}

GetEstimationValueStopStageIndex

public override int GetEstimationValueStopStageIndex()

정의

State의 가치 추정 값을 계산을 중단할 Stage Index를 설정합니다. 즉, 해당 값이 n일 경우 Stage Index가 n 이상일 경우 State 가치 추정 값을 계산하지 않습니다.

반환

Type	Description	Default
Integer	State 가치 추정 값 계산 중단을 시작할 Stage Index입니다.	Int32.MaxValue

예제 (Default Logic)

public override int GetEstimationValueStopStageIndex()
{
    return Int32.MaxValue;
}

GetStateFilteringType

public override StateFilteringType GetStateFilteringType()

정의

탐색할 State를 필터링하는 로직을 설정합니다.

반환

Type	Description	Default
StateFilteringType	State 필터링 타입입니다.	Default Logic 참조

예제 (Default Logic)

public override StateFilteringType GetStateFilteringType()
{
    return StateFilteringType.Global;
}

GetGlobalTransitionCount

public override int GetGlobalTransitionCount()

정의

Global 필터링 적용 시, 필터링 후 최종 탐색을 진행할 State 개수를 설정합니다. 예를 들어, 해당 값을 1000으로 설정할 경우, 특정 Stage에서 1000개의 State만 남기고 나머지 State는 탐색대상에서 제외합니다.

반환

Type	Description	Default
Integer	Global 필터링 후 탐색을 진행할 State 개수입니다.	1000

예제 (Default Logic)

public override int GetGlobalTransitionCount()
{
    return 1000;
}

GetApproximationTransitionCount

public override int GetApproximationTransitionCount() 

정의

근사 로직을 통한 Global 필터링 적용 시, 필터링 후 최종 탐색을 진행할 최대 State 개수를 설정합니다. 예를 들어, 해당 값을 1000으로 설정할 경우, 특정 Stage에서 최대 1000개의 State만 남기고 나머지 State는 탐색 대상에서 제외합니다.

반환

Type	Description	Default
Integer	근사 로직을 사용한 Global 필터링 후 탐색을 진행할 최대 State 개수입니다.	10

예제 (Default Logic)

public override int GetApproximationTransitionCount() 
{
    return 10;
}

GetClusterTransitionCount

public override int GetClusterTransitionCount()

정의

State Clustering 방법을 사용한 Global 필터링 적용 시, 필터링 후 최종 탐색을 진행할 State 개수를 설정합니다. 예를 들어, 해당 값을 10으로 설정할 경우, 특정 Stage에서 10개의 State만 남기고 나머지 State는 탐색대상에서 제외합니다.

반환

Type	Description	Default
Integer	State Clustering 방법을 사용한 Global 필터링 후 탐색을 진행할State 개수입니다.	2

예제 (Default Logic)

public override int GetClusterTransitionCount() 
{
    return 2;
}

GetLocalTransitionCount

public override int GetLocalTransitionCount()

정의

Local 필터링 적용 시, 필터링 후 최종 탐색을 진행할 State 개수를 설정합니다. 예를 들어, 해당 값을 1으로 설정할 경우, 특정 State로부터의 State Transition 중 1개만 선택하여 해당 State Transition에 정의된 다음 State를 탐색합니다.

반환

Type	Description	Default
Integer	Local 필터링 후 탐색을 진행할 State 개수입니다.	1

예제 (Default Logic)

public override int GetLocalTransitionCount()
{
    return 1;
}

GetGlobalFilteringStartStageIndex

public override int GetGlobalFilteringStartStageIndex()

정의

Global 필터링 로직을 적용을 시작할 Stage Index를 설정합니다. 예를 , 해당 값을 0으로 설정할 경우 Index가 0보다 크거나 같은 Stage에 모두 Global 필터링 로직이 적용됩니다.

반환

Type	Description	Default
Integer	Global 필터링 로직 적용을 시작할 Stage Index 입니다.	0

예제 (Default Logic)

public override int GetGlobalFilteringStartStageIndex()
{
    return 0;
}

GetLocalFilteringStartStageIndex

public override int GetLocalFilteringStartStageIndex()

정의

Local 필터링 로직을 적용을 시작할 Stage Index를 설정합니다. 예를 들어, 해당 값을 0으로 설정할 경우 Index가 0보다 크거나 같은 Stage에 모두 Local 필터링 로직이 적용됩니다.

반환

Type	Description	Default
Integer	Local 필터링 로직 적용을 시작할 Stage Index 입니다.	0

예제 (Default Logic)

public override int GetLocalFilteringStartStageIndex()
{
    return 0;
}

GetApproximationStartStageIndex

public override int GetApproximationStartStageIndex()

정의

근사해를 구하는 로직 적용을 시작할 Stage의 Index를 설정합니다. 예를 들어, 해당 값을 0으로 설정할 경우 Index가 0보다 크거나 같은 Stage에 모두 근사해를 구하는 로직이 적용됩니다.

반환

Type	Description	Default
Integer	근사해를 구하는 로직 적용을 시작할 Stage의 Index 입니다.	0

예시 (Default Logic)

public override int GetApproximationStartStageIndex()
{
    return 0;
}

GetMinimumTransitionCost

public override double GetMinimumTransitionCost()

정의

가능한 모든 Transition에 대하여 가장 작은 Transition cost를 설정합니다. 해당 값은 근사 로직을 통해 탐색할 State를 필터링할 때 사용되는 파라메터 입니다.

반환

Type	Description	Default
Integer	발생 가능한 가장 작은 Transition cost 입니다.	0

예제 (Default Logic)

public override double GetMinimumTransitionCost()
{
    return 0;
}

GetMultiplier

public override double GetMultiplier()

정의

근사 로직을 통해 탐색할 State를 필터링 할 때 사용되는 파라메터 입니다. 해당 값이 클수록 많은 State를 탐색하며 계산시간이 증가하고 목적함수 값이 개선될 가능성이 높아집니다.

반환

Type	Description	Default
Double	Multiplier 파라메터 값 입니다.	2

예제 (Default Logic)

public override double GetMultiplier() 
{
    return 2;
}

GetEstimatedValue

public override double GetEstimatedValue(State state)

정의

주어진 State의 가치함수 (Value function)의 추정치를 설정합니다. 해당 추정치는 근사 로직을 적용하여 탐색할 State 수를 줄이는데 사용됩니다.

매개 변수

Type	Description
State	가치함수 (Value function)의 추정치를 구할 대상 State 입니다.

반환

Type	Description	Default
Double	State의 가치함수 추정치 입니다.	Default Logic 참조

예제 (Default Logic)

public override double GetEstimatedValue(State state)
{
    double dualBound = BoundControl.Instance.GetDualBound(state);
    state.SetDualBound(dualBound);

    return state.BestValue + state.DualBound;
}

FilterGlobalStates

public override List<State> FilterGlobalStates(List<State> states, int maxTransitionCount, ObjectiveFunctionType objectiveFunctionType, double pruneTolerance, bool isApplyStateClustering)

정의

Global 필터링 로직을 정의하고 이를 통해 탐색할 State 리스트를 반환합니다.

매개 변수

Type	Description
List<State>	필터링 하기 전 State 리스트 입니다.
Integer	필터링 후 탐색을 진행할 최대 State 수 입니다.
ObjectiveFunctionType	문제의 목적함수 타입입니다. (Maximize, Minimize)
Double	State Prune 조건 판단 시 적용되는 Tolerance 값입니다.
Boolean	State Clustering 적용 여부입니다.

반환

Type	Description	Default
List<State>	필터링 후 탐색 대상이 State 리스트 입니다.	Default Logic 참조

예제 (Default Logic)

public override List<State> FilterGlobalStates(List<State> states, int maxTransitionCount, ObjectiveFunctionType objectiveFunctionType, double pruneTolerance, bool isApplyStateClustering)
{
    List<State> filtered = new List<State>();

    if (isApplyStateClustering)
    {
        Dictionary<int, List<State>> clusters = new Dictionary<int, List<State>>();
        foreach (State state in states)
        {
            if (clusters.TryGetValue(state.ClusterID, out List<State> list) == false)
            {
                clusters.Add(state.ClusterID, new List<State>() { state });
            }
            else 
            {
                list.Add(state);
            }
        }

        int clusterTransitionCount = this.GetClusterTransitionCount();
        foreach (KeyValuePair<int, List<State>> item in clusters)
        {
            List<State> list = item.Value.OrderBy(x => x.ClusterDistance).ToList();

            int maxCount = clusterTransitionCount;
            int count = 0;
            foreach (State st in list)
            {
                if (count > maxCount)
                    break;

                filtered.Add(st);

                count++;
            }
        }
    }
    else
    {
        foreach (State state in states)
        {
            if (state.IsFinal)
                continue;

            double estimatedValue = GetEstimatedValue(state);
            state.EstimationValue = estimatedValue;
        }

        if (objectiveFunctionType == ObjectiveFunctionType.Minimize)
            states = states.OrderBy(x => x.EstimationValue).ToList();
        else if (objectiveFunctionType == ObjectiveFunctionType.Maximize)
            states = states.OrderByDescending(x => x.EstimationValue).ToList();

        int count = 0;
        foreach (State state in states)
        {
            if (maxTransitionCount <= count)
                break;

            filtered.Add(state);
            count++;
        }
    }

    return filtered;
}

FilterLocalStates

public override List<State> FilterLocalStates(List<State> states, int maxTransitionCount)

정의

Local 필터링 로직을 정의하고 이를 통해 탐색할 State 리스트를 반환합니다.

매개 변수

Type	Description
List<State>	필터링 하기 전 State 리스트 입니다.
Integer	필터링 후 탐색을 진행할 최대 State 수 입니다.

반환

Type	Description	Default
List<State>	필터링 후 탐색 대상이 State 리스트 입니다.	Default Logic 참조

예제 (Default Logic)

public override List<State> FilterLocalStates(List<State> states, int maxTransitionCount)
{
    states = states.OrderBy(x => x.PrevBestState.DualBound + (x.BestValue - x.PrevBestState.BestValue) + x.BestValue).ToList();

    List<State> filtered = new List<State>();

    int count = 0;
    foreach (State state in states)
    {
        if (maxTransitionCount <= count)
            break;

        filtered.Add(state);
        count++;
    }

    return filtered;
}

CanPruneByApproximation

public override bool CanPruneByApproximation(State state, ObjectiveFunctionType objFuncType, double minEstimationValue, double minTransitionCost, double multiplier, double pruneTolerance)

정의

근사 로직을 통해 탐색할 State의 수를 줄일 때 주어진 State가 탐색 대상에서 제외될 지 여부를 설정합니다.

매개 변수

Type	Description
State	판단 대상 State 입니다.
ObjectiveFunctionType	문제의 목적함수 타입입니다. (Maximize, Minimize)
Double	탐색 후보 State들의 가치함수 근사치 중 가장 작은 값입니다.
Double	발생 가능한 가장 작은 Transition cost 입니다.
Double	Multiplier 파라메터 값 입니다.
Double	State Prune 조건 판단 시 적용되는 Tolerance 값입니다.

반환

Type	Description	Default
Boolean	대상 State Prune 여부입니다.	Default Logic 참조

예제 (Default Logic)

 public override bool CanPruneByApproximation(State state, ObjectiveFunctionType objFuncType, double minEstimationValue, double minTransitionCost, double multiplier, double pruneTolerance)
{
    if (state.IsFinal)
        return false;

    if (objFuncType == ObjectiveFunctionType.Minimize)
    {
        if (state.EstimationValue + pruneTolerance > minEstimationValue + (minTransitionCost * multiplier))
            return true;
        else
            return false;
    }
    else
    {
        if (state.EstimationValue + pruneTolerance < minEstimationValue + (minTransitionCost * multiplier))
            return true;
        else
            return false;
    }
}