C#의 최적화 알고리즘

Question

여기서부터 어디로 가야할 지 모르는 최적화 문제가 있습니다. 가장 예측 된 r 제곱 값을 리턴하는 입력의 최상의 조합을 찾으려는 프로그램이 있습니다. 문제는 내가 총 21 개의 입력 (List)을 가지고 있으며 15 개의 입력 집합에 그것들이 필요하다는 것입니다. 총 조합 수식은 다음과 같습니다.

n!/r! (n-r)! = 21!/15! (21-15)! = 54,264 가능한 조합

분명히 각 조합을 통해 실행하고 예측 된 rsquared를 계산하는 것은 이상적인 솔루션이 아니므로 더 나은 방법/알고리즘/방법을 사용하여 건너 뛰거나 나쁜 조합을 좁히려 고 시도 할 수 있습니다. 가장 적은 양의 조합 만 처리하고 있습니까? 다음은이 문제에 대한 내 현재 사이비 코드 :

public BestCombo GetBestCombo(List<List<MultipleRegressionInfo>> combosList) 
{ 
    BestCombo bestCombo = new BestCombo(); 

    foreach (var combo in combosList) 
    { 
     var predRsquared = CalculatePredictedRSquared(combo); 

     if (predRsquared > bestCombo.predRSquared) 
     { 
     bestCombo.predRSquared = predRsquared; 
     bestCombo.BestRSquaredCombo = combo; 
     } 
    } 

    return bestCombo; 
} 

public class BestCombo 
    { 
     public double predRSquared { get; set; } 
     public IEnumerable<MultipleRegressionInfo> BestRSquaredCombo { get; set; } 
    } 

public class MultipleRegressionInfo 
{ 
    public List<double> input { get; set; } 
    public List<double> output { get; set; } 
} 

public double CalculatePredictedRSquared(List<MultipleRegressionInfo> combo) 
{ 
    Matrix<double> matrix = BuildMatrix(combo.Select(i => i.input).ToArray()); 
    Vector<double> vector = BuildVector(combo.ElementAt(0).output); 
    var coefficients = CalculateWithQR(matrix, vector); 
    var y = CalculateYIntercept(coefficients, input, output); 
    var estimateList = CalculateEstimates(coefficients, y, input, output); 
    return GetPredRsquared(estimateList, output); 
} 

Answer 1

54264 컴퓨터에 대한 엄청난되지는 - 그것은 R^2을 계산하는 전화를 몇 통 타이밍이 걸릴 것입니다 얼마나 오래 볼까지 곱 가치가있을 수도 있습니다.

R^2 (A, B, C)> = R^2 (A, B)라는 사실에 의존하는 이러한 종류의 문제에 대한 분기 및 바운드 알고리즘이 있습니다. 변수를 삭제할 때만 감소합니다. 반복적으로 크기의 모든 변수 세트의 공간을 검색합니다. 변수 세트에 대해 R^2를 계산 한 후 세트에서 단일 변수를 삭제하여 생성 된 세트로 재귀 호출을 작성하십시오. 기존 간격의 오른쪽 (A.CDE는 A..DE, ACE 및 A.CD를 생성하지만 .CDE는 .BCDE가 생성하지 않습니다). 원하는 크기의 집합으로 내려 갔을 때 또는 지금까지 가장 좋은 답보다 우수하지 않은 R^2를 찾은 경우 재귀를 종료 할 수 있습니다.

지금까지 R^2 값이 가장 좋은 대답보다 좋지 않은 경우가 발생하면 시간이 절약되지만 이는 보장 할 수 없습니다. R^2가 가장 높은 집합을 조사하기 위해 chrying을 시도 할 수 있습니다. 가장 좋은 최상의 답을 찾고 나면 형제를 배제하기에 충분할 것으로 기대하고, 프로 시저를 사용하여 계산합니다 ABCDE에 대해 이미 수행 한 계산을 사용하는 A.CDE에 대한 R^2.