Tag: pareto

Grasshopper: Calculate the Pareto front in multi-objective data in C#

A method for returning a collection of Pareto-optimal data. Pareto analysis is used in multi-objective optimisation to search for potential non-dominated solutions, i.e. solutions for which there are no solutions that perform better in every objective being assessed.

pareto-front

Input a collection of data. This data is accepted as Grasshopper’s DataTree format. The ‘tree’ contains a collection of branches. Each branch contains a list. Each list corresponds to the list of objective results corresponding to a single node.

The method sorts the input data into two DataTrees: Pareto-optimal branches and non-Pareto-optimal branches.

The algorithm is simple and unsophisticated, running in O(n2). It is fine for smaller data sets, though you may wish to investigate more sophisticated algorithms for larger datasets.

C# code to find the Pareto front

  private void RunScript(DataTree<double> data, ref object opt, ref object nonopt)
  {

    DataTree<double> optimal = new DataTree<double>();
    DataTree<double> nonoptimal = new DataTree<double>();

    //data should be a tree, where each branch is equivalent to one data point, and the length of the list is equal to the number of parameters.
    for(int n = 0; n < data.BranchCount; n++) //for each node
    {
      //check it against every other node
      //we need to find one node where every parameter is superior. if not, we have pareto optimality
      bool superiornodefound = false;
      for (int i = 0; i < data.BranchCount; i++) //check node i
      {
        bool issuperior = true;
        for(int p = 0; p < data.Branch(0).Count; p++)
        {
          if(data.Branch(i)[p] > data.Branch(n)[p])
          {
            issuperior = false;
            break;
          }
        }
        if(issuperior && i != n) superiornodefound = true;
      }
      if(superiornodefound) nonoptimal.AddRange(data.Branch(n), new GH_Path(nonoptimal.BranchCount));
      else optimal.AddRange(data.Branch(n), new GH_Path(optimal.BranchCount));
    }

    //return outputs
    opt = optimal;
    nonopt = nonoptimal;

    //grasshopper-related UI
    double optimalratio = Math.Round(100.0 * optimal.BranchCount / data.BranchCount, 1);
    Component.Message = optimalratio.ToString() + "% optimal";
    Component.Description = optimalratio.ToString() + "% of solutions are Pareto optimal.";

  }