Hololens Anchor 自动布局（三）—— Black Hole Algorithm For SCP

Background

熬夜熬死了要~

总之昨夜发现了一个据说对SCP效果特棒的启发性算法-黑洞算法
Paper ：Black Hole Algorithm For SCP
具体有多好，见图：
Instance代表的数据采自 J.E.Beasley 的 OR-Library
Instances For Set Covering (OR-Library)

这个结果已经远远超过了蚁群算法(ACO)的效果：

以及效果更好的超启发的蚁群算法(ACO-HH)

Black Hole Algorithm

暂时把伪代码贴上，有精力的时候再补充和解释变量

实现Black Hole Algorithm的代码

数据结构 DataStruct.cs

 class Black_Hole
 {
     List<Anchor> anchors;
     Random random;

     public int N; //子集个数
     public int M; //元素个数
     public int PopSize;  //star个数

     public int[] c; //子集cost
     public int[][] a; //子集j是否包含元素i
     
     public int[][] x; //本次迭代的可行解集
     public int[][] x1; //下次迭代的可行解集

     enum Shape_Type { Deta, Gama }; //将实数域转换到[0,1]的实数域
     enum Transfer_Type { Standard,Static_Probability, Elitist}; //将[0,1]的实数域转换到{0，1}二进制域

     public double alpha;

     public bool Valid_Result;
     public int[] result;

     public Black_Hole()
     {
         anchors = new List<Anchor>();
     }

     public void Add(Anchor anchor)
     {
         this.anchors.Add(new Anchor(anchor.loc, anchor.models));
     }

     public void standard()
     {
         UpdateLength();

         c = new int[N];

         for (int i = 0; i < N; ++i)
         {
             c[i] = 1;
         }

         x = new int[PopSize][];
         for (int i = 0; i < PopSize; ++i)
         {
             x[i] = new int[N];
             for (int j = 0; j < N; ++j)
                 x[i][j] = 0;
         }

         x1 = new int[PopSize + 1][];
         for (int i = 0; i <= PopSize; ++i)
         {
             x1[i] = new int[N];
             for (int j = 0; j < N; ++j)
                 x1[i][j] = 0;
         }

         a = new int[PopSize + 1][];
         for (int i = 0; i <= PopSize; ++i)
         {
             a[i] = new int[N];
             for (int j = 0; j < N; ++j)
                 a[i][j] = 0;
         }

         int len;
         for (int i = 0; i < N; ++i)
         {
             len = anchors[i].models.Count();
             for (int j = 0; j < len; ++j)
             {
                 a[i][anchors[i].models[j]] = 1;
             }
         }

     }

     public void start(int T)
     {
         random = new Random();
         int[] f = new int[PopSize+1];

         for (int i = 0; i < PopSize; ++i)
         {
             for (int j = 0; j < N; ++j)
             {
                 x[i][j] = random.Next(2);
             }
             f[i] = cost(x[i], N);

         }

         int globalfit = int.MaxValue;

         int t = 0;
         while (t < T)
         {
             int minfit;
             int minindex;
             min(f, N, out minfit, out minindex);

             if (minfit < globalfit)
             {
                 globalfit = minfit;
                 for (int j = 0; j < N; ++j)
                 {
                     x[PopSize][j] = x[minindex][j];
                 }
             }

             double sum = 0;
             for (int ii = 0; ii < PopSize; ++ii)
                 sum += cost(x[ii], N);
             double R = minfit / sum;

             for (int i = 0; i < PopSize; ++i)
             {
                 double rand = random.NextDouble();
                 if (R > rand)
                     for (int j = 0; j < N; ++j)
                         x[i][j] = random.Next(2);
             }

             for (int i = 0; i < PopSize; ++i)
                 for (int j = 0; j < N; ++j)
                 {
                     double rand = random.NextDouble();
                     double tmp = x[i][j] + rand * (x[PopSize][j] - x[i][j]);
                     x1[i][j] = transfer(tmp, rand);
                 }

             UpdateIteration();
         }

         Valid_Result = true;
         result = new int[N];
         for (int i = 0; i < N; ++i)
             result[i] = x[PopSize][i];
         
     }

     private int cost(int[] x, int length)
     {
         int sum = 0;
         for (int i = 0; i < length; ++i)
             if (x[i] == 1)
                 sum++;
         return sum;
     }

     private void min(int[] f, int length, out int min, out int index)
     {
         index = -1;
         min = int.MaxValue;
         for (int i = 0; i < length; ++i)
             if (f[i] < min)
             {
                 min = f[i];
                 index = i;
             }
     }

     private double g(double tmp, Shape_Type st = Shape_Type.Deta, int type = 1)
     {
         if (st == Shape_Type.Deta)
         {
             switch (type)
             {
                 case 1: return 1 / (1 + Math.Pow(Math.E, -2 * tmp));
                 case 2: return 1 / (1 + Math.Pow(Math.E, -2 * tmp));
                 case 3: return 1 / (1 + Math.Pow(Math.E, -tmp / 2));
                 case 4: return 1 / (1 + Math.Pow(Math.E, -tmp / 3));
                 default: break;
             }
             return -1;
         }
         else if (st == Shape_Type.Gama)
         {
             switch (type)
             {
                 case 1: return Math.Abs(Erf(Math.Sqrt(Math.PI) / 2 * tmp));
                 case 2: return Math.Abs(Math.Tanh(tmp));
                 case 3: return Math.Abs(tmp / Math.Sqrt(1 + tmp * tmp));
                 case 4: return Math.Abs(2 / Math.PI * Math.Atan(Math.PI / 2 * tmp));
                 default: break;
             }
             return -1;
         }
         return -1;
     }

     private int transfer(double tmp,double rand, Transfer_Type tt =Transfer_Type.Standard)
     {
         if(tt == Transfer_Type.Standard)
         {
             if (rand < tmp)
                 return 1;
             else
                 return 0;
         }
         return -1;
     }

     private void UpdateLength()
     {
         M = 0;
         N = anchors.Count();
         for (int i = 0; i < N; ++i)
         {
             int len = anchors[i].models.Count();
             for (int j = 0; j < len; ++j)
             {
                 if (anchors[i].models[j] > M)
                 {
                     PopSize = anchors[i].models[j];
                 }
             }
         }
         M++;
     }

     private void UpdateIteration()
     {
         for (int i = 0; i < PopSize; ++i)
             for (int j = 0; j < N; ++j)
                 x[i][j] = x1[i][j];
     }

     private static double Erf(double x)
     {
         double result = 0;
         int index = 0;
         do
         {
             index++;
         } while (x / Math.Pow(10, index) > 1e-3);//设置计算精度
         int maxIndex = (int)Math.Pow(10, index);
         double deltaX = x / maxIndex;
         for (int i = 0; i <= maxIndex; i++)
         {
             if (i > 0 && i < maxIndex)
             {
                 result += 2 * Math.Exp(-Math.Pow(deltaX * i, 2));
                 continue;
             }
             else if (i == maxIndex)
             {
                 result += Math.Exp(-Math.Pow(deltaX * i, 2));
                 continue;
             }
             else if (i == 0)
             {
                 result += Math.Exp(-Math.Pow(deltaX * i, 2));
                 continue;
             }
         }
         return result * deltaX / Math.Pow(Math.PI, 0.5);

     }
     
}

主程序 MainWindows.xaml.cs

Black_Hole black_hole = new Black_Hole();

const int T = 50;

public void BH()
{
    int[] result = new int[paths.Count()];
    ConvertModelsToBH(paths);
    if (BHStart(ref result))
    {
        String ss = "";
        //some operations based on "result" array
        for (int i = 0; i < result.Count(); ++i)
        {
            ss += result[i].ToString();

        }
        System.Windows.MessageBox.Show(ss);
    }
}

void ConvertModelsToBH(List<BaoPath> paths)
{
    for (int i = 0; i < maxn; ++i)
        for (int j = 0; j < maxn; ++j)
        {
            pixels[i, j].value = 0;
            pixels[i, j].id = "";

        }


    int radius = 75;//这个值要 equals 现实中的3米

    int length = WallAndModelList.Count();

    #region loop
    for (int i = 0; i < length; ++i)
    {
        BaoModel bm = WallAndModelList[i];
        PointD center = new PointD(bm.x, bm.y);

        List<BaoSide> PointVis = new List<BaoSide>();
        GetsVisibleRegion(center.X, center.Y, false, ref PointVis);

        for (int ii = BInt(center.Y - radius, true); ii <= BInt(center.Y, false); ++ii)
        {
            double j_tmp = Math.Sqrt(radius * radius - (center.Y - ii) * (center.Y - ii));
            for (int jj = BInt(center.X - j_tmp, true); jj <= BInt(center.X + j_tmp, false); ++jj)
            {
                if (IsPointInPolygon(jj, ii, PointVis))
                {
                    pixels[jj, ii].Add(WallAndModelList[i].value, WallAndModelList[i].id); //可能有问题
                }

            }
        }
        for (int ii = BInt(center.Y + 1, false); ii <= BInt(center.Y + radius, false); ++ii)
        {
            double j_tmp = Math.Sqrt(radius * radius - (ii - center.Y) * (ii - center.Y));
            for (int jj = BInt(center.X - j_tmp, true); jj <= BInt(center.X + j_tmp, false); ++jj)
            {
                if (IsPointInPolygon(jj, ii, PointVis))
                {
                    pixels[jj, ii].Add(WallAndModelList[i].value, WallAndModelList[i].id); //可能有问题
                }
            }
        }

    }
    #endregion

    int bias = 31;

    double last_value = -1;
    string last_string = "null";
    // int fi = -1;
    // int fj = -1;

    Anchor anchor;
    List<int> models = new List<int>();

    for (int i = 0; i < maxn; ++i)
        for (int j = 0; j < maxn; ++j)
        {
            if (pixels[i, j].value != 0 && (!pixels[i, j].id.Equals(last_string) || pixels[i, j].value != last_value))
            {
                String[] ss = pixels[i, j].id.Split(',');
                int len = ss.Count();
                for (int k = 0; k < len; ++k)
                {
                    if (ss[k].Count() != 0)
                        models.Add(int.Parse(ss[i].ToString()) + bias);
                }
                anchor = new Anchor(new PointD(i, j), models);
                black_hole.Add(anchor);
            }
        }


}

bool BHStart(ref int[] result)
{
    int length = black_hole.N;
    black_hole.standard();
    black_hole.start(T);
    if (black_hole.Valid_Result)
    {
        for (int i = 0; i < length; ++i)
            result[i] = black_hole.result[i];
        return true;
    }
    return false;
}