Free cookie consent management tool by TermsFeed Policy Generator

Changeset 9945 for branches


Ignore:
Timestamp:
09/10/13 21:06:55 (11 years ago)
Author:
ascheibe
Message:

#1886

  • added new convex hull algorithm based on SMO/SVM
  • added unit test and a visualization
  • updated MIConvexHull
Location:
branches/HeuristicLab.Analysis.AlgorithmBehavior
Files:
17 added
8 edited

Legend:

Unmodified
Added
Removed

  • branches/HeuristicLab.Analysis.AlgorithmBehavior

    • Property svn:global-ignores set to
      HeuristicLab.Analysis.AlgorithmBehavior.sln.DotSettings.user

  • branches/HeuristicLab.Analysis.AlgorithmBehavior/AlgorithmBehaviorUnitTests/AlgorithmBehaviorUnitTests.csproj

    r9754 r9945  
    5858      <RequiredTargetFramework>3.5</RequiredTargetFramework>
    5959    </Reference>
     60    <Reference Include="System.Data" />
     61    <Reference Include="System.Drawing" />
     62    <Reference Include="System.Windows.Forms" />
     63    <Reference Include="System.Xml" />
    6064  </ItemGroup>
    6165  <Choose>
    … …  
    7579    <Compile Include="UnitTest1.cs" />
    7680    <Compile Include="Properties\AssemblyInfo.cs" />
     81    <Compile Include="ConvexHullTest.cs" />
    7782  </ItemGroup>
    7883  <ItemGroup>
    … …  
    8489      <Project>{2533d1f9-f7f6-46cb-90d2-76d254e38dee}</Project>
    8590      <Name>HeuristicLab.Analysis.AlgorithmBehavior.Analyzers-3.3</Name>
     91    </ProjectReference>
     92    <ProjectReference Include="..\MIConvexHull\MIConvexHull.csproj">
     93      <Project>{2337776d-7d0c-40aa-a439-c26c3ce24fab}</Project>
     94      <Name>MIConvexHull</Name>
    8695    </ProjectReference>
    8796  </ItemGroup>

  • branches/HeuristicLab.Analysis.AlgorithmBehavior/HeuristicLab.Analysis.AlgorithmBehavior.Analyzers.Views/3.3/ConvexHullView.cs

    r9789 r9945  
    5050      var sols = Content.GetSolutionsFromGeneration(1);
    5151      var input = sols.Select(x => ConvertPermutationToVertex(x.GetPermutation()));
    52       var result = ConvexHull.Create(input);
     52      //TODO: HyperHull.Calculate(Content);
     53      //HyperHull.CalculateUsingSMO(Content.GetSolutionsFromGeneration(1));
     54
     55
     56      //var result = ConvexHull.Create(input);
     57
    5358      //TODO
    5459    }

  • branches/HeuristicLab.Analysis.AlgorithmBehavior/HeuristicLab.Analysis.AlgorithmBehavior.Analyzers.Views/3.3/HeuristicLab.Analysis.AlgorithmBehavior.Analyzers.Views-3.3.csproj

    r9791 r9945  
    104104      <Private>False</Private>
    105105    </Reference>
     106    <Reference Include="HeuristicLab.Problems.DataAnalysis.Symbolic.Classification-3.4, Version=3.4.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
     107      <SpecificVersion>False</SpecificVersion>
     108      <HintPath>..\..\..\..\trunk\sources\bin\HeuristicLab.Problems.DataAnalysis.Symbolic.Classification-3.4.dll</HintPath>
     109      <Private>False</Private>
     110    </Reference>
    106111    <Reference Include="HeuristicLab.Problems.Instances-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
    107112      <SpecificVersion>False</SpecificVersion>

  • branches/HeuristicLab.Analysis.AlgorithmBehavior/HeuristicLab.Analysis.AlgorithmBehavior.Analyzers/3.3/HeuristicLab.Analysis.AlgorithmBehavior.Analyzers-3.3.csproj

    r9754 r9945  
    3838  </PropertyGroup>
    3939  <ItemGroup>
    40     <Reference Include="ALGLIB-3.6.0, Version=3.6.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
     40    <Reference Include="HeuristicLab.Algorithms.DataAnalysis-3.4, Version=3.4.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
     41      <SpecificVersion>False</SpecificVersion>
     42      <HintPath>..\..\..\..\trunk\sources\bin\HeuristicLab.Algorithms.DataAnalysis-3.4.dll</HintPath>
    4143      <Private>False</Private>
    4244    </Reference>
    … …  
    9092      <Private>False</Private>
    9193    </Reference>
     94    <Reference Include="HeuristicLab.Problems.DataAnalysis-3.4, Version=3.4.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
     95      <SpecificVersion>False</SpecificVersion>
     96      <HintPath>..\..\..\..\trunk\sources\bin\HeuristicLab.Problems.DataAnalysis-3.4.dll</HintPath>
     97      <Private>False</Private>
     98    </Reference>
     99    <Reference Include="HeuristicLab.Problems.Instances-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
     100      <SpecificVersion>False</SpecificVersion>
     101      <HintPath>..\..\..\..\trunk\sources\bin\HeuristicLab.Problems.Instances-3.3.dll</HintPath>
     102      <Private>False</Private>
     103    </Reference>
    92104    <Reference Include="System" />
    93105    <Reference Include="System.Core" />
    … …  
    113125    <Compile Include="CombinedOperators\QAPAfterMutationCombinedOperator.cs" />
    114126    <Compile Include="CombinedOperators\QAPAfterCrossoverCombinedOperator.cs" />
     127    <Compile Include="HyperHull.cs" />
    115128    <Compile Include="SolutionsCaching\AfterCrossoverSolutionCachingAnalyzer.cs" />
    116129    <Compile Include="SolutionsCaching\SolutionCachingAnalyzer.cs" />
    … …  
    121134    <Compile Include="SelectionPressureAnalyzer.cs" />
    122135    <Compile Include="SolutionsCaching\PermutationInformation.cs" />
     136    <Compile Include="SVM.cs" />
    123137    <Compile Include="WorstQualityAnalyzer.cs" />
    124138    <Compile Include="InitializableOperator.cs" />

  • branches/HeuristicLab.Analysis.AlgorithmBehavior/HeuristicLab.Analysis.AlgorithmBehavior.sln

    r9730 r9945  
    1717EndProject
    1818Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "MIConvexHull", "MIConvexHull\MIConvexHull.csproj", "{2337776D-7D0C-40AA-A439-C26C3CE24FAB}"
     19EndProject
     20Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "Visualization", "Visualization\Visualization.csproj", "{E968DFEC-F612-4898-B92A-00A45E2DEE85}"
    1921EndProject
    2022Global
    … …  
    7274    {2337776D-7D0C-40AA-A439-C26C3CE24FAB}.Release|x64.ActiveCfg = Release|Any CPU
    7375    {2337776D-7D0C-40AA-A439-C26C3CE24FAB}.Release|x86.ActiveCfg = Release|Any CPU
     76    {E968DFEC-F612-4898-B92A-00A45E2DEE85}.Debug|Any CPU.ActiveCfg = Debug|Any CPU
     77    {E968DFEC-F612-4898-B92A-00A45E2DEE85}.Debug|Any CPU.Build.0 = Debug|Any CPU
     78    {E968DFEC-F612-4898-B92A-00A45E2DEE85}.Debug|x64.ActiveCfg = Debug|Any CPU
     79    {E968DFEC-F612-4898-B92A-00A45E2DEE85}.Debug|x86.ActiveCfg = Debug|Any CPU
     80    {E968DFEC-F612-4898-B92A-00A45E2DEE85}.Release|Any CPU.ActiveCfg = Release|Any CPU
     81    {E968DFEC-F612-4898-B92A-00A45E2DEE85}.Release|Any CPU.Build.0 = Release|Any CPU
     82    {E968DFEC-F612-4898-B92A-00A45E2DEE85}.Release|x64.ActiveCfg = Release|Any CPU
     83    {E968DFEC-F612-4898-B92A-00A45E2DEE85}.Release|x86.ActiveCfg = Release|Any CPU
    7484  EndGlobalSection
    7585  GlobalSection(SolutionProperties) = preSolution

  • branches/HeuristicLab.Analysis.AlgorithmBehavior/MIConvexHull/ConvexHull/ConvexFaceInternal.cs

    r9730 r9945  
    4040            return x.Index.CompareTo(y.Index);
    4141        }
     42    }
     43
     44    /// <summary>
     45    /// For deferred face addition.
     46    /// </summary>
     47    sealed class DeferredFace
     48    {
     49        /// <summary>
     50        /// The faces.
     51        /// </summary>
     52        public ConvexFaceInternal Face, Pivot, OldFace;
     53
     54        /// <summary>
     55        /// The indices.
     56        /// </summary>
     57        public int FaceIndex, PivotIndex;
    4258    }
    4359

  • branches/HeuristicLab.Analysis.AlgorithmBehavior/MIConvexHull/ConvexHull/ConvexHullInternal.cs

    r9730 r9945  
    4242        VertexBuffer BeyondBuffer;
    4343        List<ConvexFaceInternal> AffectedFaceBuffer;
     44        List<DeferredFace> ConeFaceBuffer;
     45        Stack<DeferredFace> ConeFaceStack;
     46        HashSet<VertexWrap> SingularVertices;
    4447
    4548        const int ConnectorTableSize = 2017;
    … …  
    6972            EmptyBuffer = new VertexBuffer();
    7073            AffectedFaceBuffer = new List<ConvexFaceInternal>();
     74            ConeFaceBuffer = new List<DeferredFace>();
     75            ConeFaceStack = new Stack<DeferredFace>();
     76            SingularVertices = new HashSet<VertexWrap>();
    7177            BeyondBuffer = new VertexBuffer();
    7278
    … …  
    130136        /// <param name="face"></param>
    131137        /// <returns></returns>
    132         private void CalculateFacePlane(ConvexFaceInternal face)
     138        private bool CalculateFacePlane(ConvexFaceInternal face)
    133139        {
    134140            var vertices = face.Vertices;
    … …  
    136142            FindNormalVector(vertices, normal);
    137143
    138             if (double.IsNaN(normal[0])) ThrowSingular();
     144            if (double.IsNaN(normal[0]))
     145            {
     146                return false;
     147                //ThrowSingular();
     148            }
    139149
    140150            double offset = 0.0;
    … …  
    157167            }
    158168            else face.IsNormalFlipped = false;
     169
     170            return true;
    159171        }
    160172       
    … …  
    318330
    319331        /// <summary>
     332        /// Creates a new deferred face.
     333        /// </summary>
     334        /// <param name="face"></param>
     335        /// <param name="faceIndex"></param>
     336        /// <param name="pivot"></param>
     337        /// <param name="pivotIndex"></param>
     338        /// <param name="oldFace"></param>
     339        /// <returns></returns>
     340        DeferredFace GetDeferredFace(ConvexFaceInternal face, int faceIndex, ConvexFaceInternal pivot, int pivotIndex, ConvexFaceInternal oldFace)
     341        {
     342            var ret = ConeFaceStack.Count > 0 ? ConeFaceStack.Pop() : new DeferredFace();
     343           
     344            ret.Face = face;
     345            ret.FaceIndex = faceIndex;
     346            ret.Pivot = pivot;
     347            ret.PivotIndex = pivotIndex;
     348            ret.OldFace = oldFace;
     349
     350            return ret;
     351        }
     352
     353        /// <summary>
    320354        /// Connect faces using a connector.
    321355        /// </summary>
    … …  
    326360            var list = ConnectorTable[index];
    327361
    328             int count = 0;
    329362            for (var current = list.First; current != null; current = current.Next)
    330363            {
    … …  
    347380        /// Removes the faces "covered" by the current vertex and adds the newly created ones.
    348381        /// </summary>
    349         private void CreateCone()
    350         {
    351             var oldFaces = AffectedFaceBuffer;
    352 
     382        private bool CreateCone()
     383        {
    353384            var currentVertexIndex = CurrentVertex.Index;
    354 
    355             for (int fIndex = 0; fIndex < oldFaces.Count; fIndex++)
    356             {
    357                 var oldFace = oldFaces[fIndex];
     385            ConeFaceBuffer.Clear();
     386
     387            for (int fIndex = 0; fIndex < AffectedFaceBuffer.Count; fIndex++)
     388            {
     389                var oldFace = AffectedFaceBuffer[fIndex];
    358390
    359391                // Find the faces that need to be updated
    … …  
    368400                        ++updateCount;
    369401                    }
    370                 }
    371 
    372                 // Recycle the face for future use
    373                 if (updateCount == 0)
    374                 {
    375                     // If the face is present in the unprocessed list, remove it
    376                     UnprocessedFaces.Remove(oldFace);
    377 
    378                     RecycleFace(oldFace);
    379                     RecycledFaceStack.Push(oldFace);
    380402                }
    381403
    … …  
    402424                    VertexWrap[] vertices;
    403425
    404                     // Recycle the oldFace
    405                     if (i == updateCount - 1)
    406                     {
    407                         RecycleFace(oldFace);
    408                         newFace = oldFace;
    409                         vertices = newFace.Vertices;
    410                         oldVertexIndex = vertices[forbidden].Index;
    411                     }
    412                     else // Pop a face from the recycled stack or create a new one
    413                     {
    414                         newFace = GetNewFace();
    415                         vertices = newFace.Vertices;                       
    416                         for (int j = 0; j < Dimension; j++) vertices[j] = oldFace.Vertices[j];
    417                         oldVertexIndex = vertices[forbidden].Index;
    418                     }
     426                    newFace = GetNewFace();
     427                    vertices = newFace.Vertices;                       
     428                    for (int j = 0; j < Dimension; j++) vertices[j] = oldFace.Vertices[j];
     429                    oldVertexIndex = vertices[forbidden].Index;
    419430
    420431                    int orderedPivotIndex;
    … …  
    450461                    vertices[orderedPivotIndex] = CurrentVertex;
    451462
    452                     CalculateFacePlane(newFace);
    453                     newFace.AdjacentFaces[orderedPivotIndex] = adjacentFace;
    454                     adjacentFace.AdjacentFaces[oldFaceAdjacentIndex] = newFace;
    455 
    456                     // let there be a connection.
    457                     for (int j = 0; j < Dimension; j++)
     463                    if (!CalculateFacePlane(newFace))
    458464                    {
    459                         if (j == orderedPivotIndex) continue;
    460                         var connector = GetNewConnector();
    461                         connector.Update(newFace, j, Dimension);
    462                         ConnectFace(connector);
     465                        return false;
    463466                    }
    464                    
    465                     // This could slightly help...
    466                     if (adjacentFace.VerticesBeyond.Count < oldFace.VerticesBeyond.Count)
    467                     {
    468                         FindBeyondVertices(newFace, adjacentFace.VerticesBeyond, oldFace.VerticesBeyond);
    469                     }
    470                     else
    471                     {
    472                         FindBeyondVertices(newFace, oldFace.VerticesBeyond, adjacentFace.VerticesBeyond);
    473                     }
    474 
    475                     // This face will definitely lie on the hull
    476                     if (newFace.VerticesBeyond.Count == 0)
    477                     {
    478                         ConvexFaces.Add(newFace);
    479                         UnprocessedFaces.Remove(newFace);
    480                         EmptyBufferStack.Push(newFace.VerticesBeyond);
    481                         newFace.VerticesBeyond = EmptyBuffer;
    482                     }
    483                     else // Add the face to the list
    484                     {
    485                         UnprocessedFaces.Add(newFace);
    486                     }
    487                 }
     467
     468                    ConeFaceBuffer.Add(GetDeferredFace(newFace, orderedPivotIndex, adjacentFace, oldFaceAdjacentIndex, oldFace));
     469                }
     470            }
     471           
     472            return true;
     473        }
     474
     475        /// <summary>
     476        /// Commits a cone and adds a vertex to the convex hull.
     477        /// </summary>
     478        void CommitCone()
     479        {
     480            // Add the current vertex.
     481            ConvexHull.Add(CurrentVertex);
     482           
     483            // Fill the adjacency.
     484            for (int i = 0; i < ConeFaceBuffer.Count; i++)
     485            {
     486                var face = ConeFaceBuffer[i];
     487
     488                var newFace = face.Face;
     489                var adjacentFace = face.Pivot;
     490                var oldFace = face.OldFace;
     491                var orderedPivotIndex = face.FaceIndex;
     492
     493                newFace.AdjacentFaces[orderedPivotIndex] = adjacentFace;
     494                adjacentFace.AdjacentFaces[face.PivotIndex] = newFace;
     495
     496                // let there be a connection.
     497                for (int j = 0; j < Dimension; j++)
     498                {
     499                    if (j == orderedPivotIndex) continue;
     500                    var connector = GetNewConnector();
     501                    connector.Update(newFace, j, Dimension);
     502                    ConnectFace(connector);
     503                }
     504
     505                // This could slightly help...
     506                if (adjacentFace.VerticesBeyond.Count < oldFace.VerticesBeyond.Count)
     507                {
     508                    FindBeyondVertices(newFace, adjacentFace.VerticesBeyond, oldFace.VerticesBeyond);
     509                }
     510                else
     511                {
     512                    FindBeyondVertices(newFace, oldFace.VerticesBeyond, adjacentFace.VerticesBeyond);
     513                }
     514
     515                // This face will definitely lie on the hull
     516                if (newFace.VerticesBeyond.Count == 0)
     517                {
     518                    ConvexFaces.Add(newFace);
     519                    UnprocessedFaces.Remove(newFace);
     520                    EmptyBufferStack.Push(newFace.VerticesBeyond);
     521                    newFace.VerticesBeyond = EmptyBuffer;
     522                }
     523                else // Add the face to the list
     524                {
     525                    UnprocessedFaces.Add(newFace);
     526                }
     527
     528                // recycle the object.
     529                ConeFaceStack.Push(face);
     530            }
     531
     532            // Recycle the affected faces.
     533            for (int fIndex = 0; fIndex < AffectedFaceBuffer.Count; fIndex++)
     534            {
     535                var face = AffectedFaceBuffer[fIndex];
     536                UnprocessedFaces.Remove(face);
     537                RecycleFace(face);
     538                RecycledFaceStack.Push(face);
    488539            }
    489540        }
    … …  
    698749        void UpdateCenter()
    699750        {
    700             for (int i = 0; i < Dimension; i++) Center[i] *= (ConvexHull.Count - 1);
    701             double f = 1.0 / ConvexHull.Count;
     751            var count = ConvexHull.Count + 1;
     752            for (int i = 0; i < Dimension; i++) Center[i] *= (count - 1);
     753            double f = 1.0 / count;
    702754            for (int i = 0; i < Dimension; i++) Center[i] = f * (Center[i] + CurrentVertex.PositionData[i]);
     755        }
     756
     757        /// <summary>
     758        /// Removes the last vertex from the center.
     759        /// </summary>
     760        void RollbackCenter()
     761        {
     762            var count = ConvexHull.Count + 1;
     763            for (int i = 0; i < Dimension; i++) Center[i] *= count;
     764            double f = 1.0 / (count - 1);
     765            for (int i = 0; i < Dimension; i++) Center[i] = f * (Center[i] - CurrentVertex.PositionData[i]);
    703766        }
    704767
    … …  
    715778            {
    716779                CurrentVertex = vertex;
     780                // update center must be called before adding the vertex.
     781                UpdateCenter();
    717782                ConvexHull.Add(CurrentVertex);
    718                 UpdateCenter();
    719783                InputVertices.Remove(vertex);
    720784
    … …  
    767831            for (int i = 2; i <= Dimension; i++)
    768832            {
    769                 double maximum = 0.0001;
     833                double maximum = 0.000001;
    770834                VertexWrap maxPoint = null;
    771835                for (int j = 0; j < extremes.Count; j++)
    … …  
    817881        double GetSimplexVolume(VertexWrap pivot, List<VertexWrap> initialPoints)
    818882        {
    819             var dim = initialPoints.Count;
    820             var m = nDMatrix;
    821 
    822             for (int i = 0; i < dim; i++)
    823             {
    824                 var pts = initialPoints[i];
    825                 for (int j = 0; j < dim; j++) m[i, j] = pts.PositionData[j] - pivot.PositionData[j];
    826             }
    827 
    828             return Math.Abs(StarMath.determinantDestructive(m, dim));
     883            var initPtsNum = initialPoints.Count;
     884            //var m = nDMatrix;
     885            var sum = 0.0;
     886       
     887            for (int i = 0; i < initPtsNum; i++)
     888            {
     889                var initPt = initialPoints[i];
     890                for (int j = 0; j < Dimension; j++)
     891                    sum += (initPt.PositionData[j] - pivot.PositionData[j])
     892                        * (initPt.PositionData[j] - pivot.PositionData[j]);
     893            }
     894
     895            return sum;
    829896        }
    830897
    … …  
    878945
    879946        /// <summary>
     947        /// Handles singular vertex.
     948        /// </summary>
     949        void HandleSingular()
     950        {
     951            RollbackCenter();
     952            SingularVertices.Add(CurrentVertex);
     953
     954            // This means that all the affected faces must be on the hull and that all their "vertices beyond" are singular.
     955            for (int fIndex = 0; fIndex < AffectedFaceBuffer.Count; fIndex++)
     956            {
     957                var face = AffectedFaceBuffer[fIndex];
     958                var vb = face.VerticesBeyond;
     959                for (int i = 0; i < vb.Count; i++)
     960                {
     961                    SingularVertices.Add(vb[i]);
     962                }
     963
     964                ConvexFaces.Add(face);
     965                UnprocessedFaces.Remove(face);
     966                EmptyBufferStack.Push(face.VerticesBeyond);
     967                face.VerticesBeyond = EmptyBuffer;
     968            }
     969        }
     970
     971        /// <summary>
    880972        /// Fins the convex hull.
    881973        /// </summary>
    … …  
    890982                var currentFace = UnprocessedFaces.First;
    891983                CurrentVertex = currentFace.FurthestVertex;
    892                 ConvexHull.Add(CurrentVertex);
     984                                               
    893985                UpdateCenter();
    894986
    … …  
    897989
    898990                // Create the cone from the currentVertex and the affected faces horizon.
    899                 CreateCone();
     991                if (!SingularVertices.Contains(CurrentVertex) && CreateCone()) CommitCone();
     992                else HandleSingular();
    900993
    901994                // Need to reset the tags
Note: See TracChangeset for help on using the changeset viewer.