2024年4月

实现效果

今天以一个交互式小球的例子跟大家分享一下wpf动画中
DoubleAnimation
的基本使用。该小球会移动到我们鼠标左键或右键点击的地方。

该示例的实现效果如下所示:

实现效果

页面设计

xaml如下所示:

<Window x:Class="AnimationDemo.MainWindow"
        xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
        xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
        xmlns:d="http://schemas.microsoft.com/expression/blend/2008"
        xmlns:mc="http://schemas.openxmlformats.org/markup-compatibility/2006"
        xmlns:local="clr-namespace:AnimationDemo"
        mc:Ignorable="d"
        Title="MainWindow" Height="450" Width="800">
    <DockPanel>
        <Border x:Name="_containerBorder" Background="Transparent">
            <Ellipse x:Name="_interactiveEllipse"
         Fill="Lime"
         Stroke="Black"
         StrokeThickness="2.0"
         Width="25"
         Height="25"
         HorizontalAlignment="Left"
         VerticalAlignment="Top" />
        </Border>
    </DockPanel>
</Window>

就是在
DockPanel
中包含一个
Border
,在
Border
中包含一个圆形。

页面设计的效果如下所示:

image-20240401095600816

一些设置

相关设置的cs代码如下所示:

   public partial class MainWindow : Window
 {
     private readonly TranslateTransform _interactiveTranslateTransform;
     public MainWindow()
     {
         InitializeComponent();

         _interactiveTranslateTransform = new TranslateTransform();

         _interactiveEllipse.RenderTransform =
             _interactiveTranslateTransform;

         _containerBorder.MouseLeftButtonDown +=
            border_mouseLeftButtonDown;
         _containerBorder.MouseRightButtonDown +=
             border_mouseRightButtonDown;
     }
 private readonly TranslateTransform _interactiveTranslateTransform;

首先声明了一个私有的只读的
TranslateTransform
类型的对象
_interactiveTranslateTransform
,然后在MainWindow的构造函数中赋值。

 _interactiveTranslateTransform = new TranslateTransform();

TranslateTransform
是什么?有什么作用呢?

image-20240401100405500

它的基本结构:

 //
 // 摘要:
 //     Translates (moves) an object in the 2-D x-y coordinate system.
 public sealed class TranslateTransform : Transform
 {

     public static readonly DependencyProperty XProperty;
  
     public static readonly DependencyProperty YProperty;

     public TranslateTransform();
   
     public TranslateTransform(double offsetX, double offsetY);

     public override Matrix Value { get; }
   
     public double X { get; set; }
  
     public double Y { get; set; }

     public TranslateTransform Clone();
 
     public TranslateTransform CloneCurrentValue();
     protected override Freezable CreateInstanceCore();
 }

TranslateTransform 是 WPF 中的一个类,它表示一个 2D 平移变换。这个类是 Transform 类的派生类,用于在 2D 平面上移动(平移)对象。
TranslateTransform 类有两个主要的属性:X 和 Y,它们分别表示在 X 轴和 Y 轴上的移动距离。例如,如果你设置 X 为 100 和 Y 为 200,那么应用这个变换的元素将会向右移动 100 像素,向下移动 200 像素。

 _interactiveEllipse.RenderTransform =
             _interactiveTranslateTransform;


_interactiveEllipse
元素的
RenderTransform
属性设置为
_interactiveTranslateTransform

image-20240401106666661864

RenderTransform
属性用于获取或设置影响
UIElement
呈现位置的转换信息。

 _containerBorder.MouseLeftButtonDown +=
    border_mouseLeftButtonDown;
 _containerBorder.MouseRightButtonDown +=
     border_mouseRightButtonDown;

这是在注册
_containerBorder
的鼠标左键点击事件与鼠标右键点击事件。

image-20240401101323899

image-20240401101401446

注意当Border这样写时,不会触发鼠标点击事件:

 <Border x:Name="_containerBorder">

这是因为在 WPF 中,Border 控件的背景默认是透明的,这意味着它不会接收鼠标事件。当你设置了背景颜色后,Border 控件就会开始接收鼠标事件,因为它现在有了一个可见的背景。
如果你希望 Border 控件在没有背景颜色的情况下也能接收鼠标事件,你可以将背景设置为透明色。这样,虽然背景看起来是透明的,但它仍然会接收鼠标事件。

可以这样设置:

<Border x:Name="_containerBorder" Background="Transparent">

鼠标点击事件处理程序

以鼠标左键点击事件处理程序为例,进行说明:

  private void border_mouseLeftButtonDown(object sender, MouseButtonEventArgs e)
  {
      var clickPoint = Mouse.GetPosition(_containerBorder);

      // Set the target point so the center of the ellipse
      // ends up at the clicked point.
      var targetPoint = new Point
      {
          X = clickPoint.X - _interactiveEllipse.Width / 2,
          Y = clickPoint.Y - _interactiveEllipse.Height / 2
      };

      // Animate to the target point.
      var xAnimation =
          new DoubleAnimation(targetPoint.X,
              new Duration(TimeSpan.FromSeconds(4)));
      _interactiveTranslateTransform.BeginAnimation(
          TranslateTransform.XProperty, xAnimation, HandoffBehavior.SnapshotAndReplace);

      var yAnimation =
          new DoubleAnimation(targetPoint.Y,
              new Duration(TimeSpan.FromSeconds(4)));
      _interactiveTranslateTransform.BeginAnimation(
          TranslateTransform.YProperty, yAnimation, HandoffBehavior.SnapshotAndReplace);

      // Change the color of the ellipse.
      _interactiveEllipse.Fill = Brushes.Lime;
  }

重点是:

 // Animate to the target point.
      var xAnimation =
          new DoubleAnimation(targetPoint.X,
              new Duration(TimeSpan.FromSeconds(4)));
      _interactiveTranslateTransform.BeginAnimation(
          TranslateTransform.XProperty, xAnimation, HandoffBehavior.SnapshotAndReplace);

      var yAnimation =
          new DoubleAnimation(targetPoint.Y,
              new Duration(TimeSpan.FromSeconds(4)));
      _interactiveTranslateTransform.BeginAnimation(
          TranslateTransform.YProperty, yAnimation, HandoffBehavior.SnapshotAndReplace);

DoubleAnimation
类的介绍:

image-20240401102112194

DoubleAnimation 是 WPF 中的一个类,它用于创建从一个 double 值到另一个 double 值的动画。这个类是 AnimationTimeline 类的派生类,它可以用于任何接受 double 类型的依赖属性。
DoubleAnimation 类有几个重要的属性:
• From:动画的起始值。
• To:动画的结束值。
• By:动画的增量值,用于从 From 值增加或减少。
• Duration:动画的持续时间。
• AutoReverse:一个布尔值,指示动画是否在到达 To 值后反向运行回 From 值。
• RepeatBehavior:定义动画的重复行为,例如,它可以设置为无限重复或重复特定的次数。

  var xAnimation =
          new DoubleAnimation(targetPoint.X,
              new Duration(TimeSpan.FromSeconds(4)));

我们使用的是这种形式的重载:

image-20240401102332146

设置了一个要达到的double类型值与达到的时间,这里设置为了4秒。

 _interactiveTranslateTransform.BeginAnimation(
          TranslateTransform.XProperty, xAnimation, HandoffBehavior.SnapshotAndReplace);

image-20240401102753637

• _interactiveTranslateTransform.BeginAnimation:这是 BeginAnimation 方法的调用,它开始一个动画,该动画会改变一个依赖属性的值。在这个例子中,改变的是 _interactiveTranslateTransform 对象的 X 属性。
• TranslateTransform.XProperty:这是 TranslateTransform 类的 X 依赖属性。这个属性表示在 X 轴上的移动距离。
• xAnimation:这是一个 DoubleAnimation 对象,它定义了动画的目标值和持续时间。在这个例子中,动画的目标值是鼠标点击的位置,持续时间是 4 秒。
• HandoffBehavior.SnapshotAndReplace:这是 HandoffBehavior 枚举的一个值,它定义了当新动画开始时,如何处理正在进行的动画。SnapshotAndReplace 表示新动画将替换旧动画,并从旧动画当前的值开始。

全部代码

xaml:

<Window x:Class="AnimationDemo.MainWindow"
        xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
        xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
        xmlns:d="http://schemas.microsoft.com/expression/blend/2008"
        xmlns:mc="http://schemas.openxmlformats.org/markup-compatibility/2006"
        xmlns:local="clr-namespace:AnimationDemo"
        mc:Ignorable="d"
        Title="MainWindow" Height="450" Width="800">
    <DockPanel>
        <Border x:Name="_containerBorder" Background="Transparent">
            <Ellipse x:Name="_interactiveEllipse"
         Fill="Lime"
         Stroke="Black"
         StrokeThickness="2.0"
         Width="25"
         Height="25"
         HorizontalAlignment="Left"
         VerticalAlignment="Top" />
        </Border>
    </DockPanel>
</Window>

cs:

using System.Text;
using System.Windows;
using System.Windows.Controls;
using System.Windows.Data;
using System.Windows.Documents;
using System.Windows.Input;
using System.Windows.Media;
using System.Windows.Media.Animation;
using System.Windows.Media.Imaging;
using System.Windows.Navigation;
using System.Windows.Shapes;

namespace AnimationDemo
{
    /// <summary>
    /// Interaction logic for MainWindow.xaml
    /// </summary>
    public partial class MainWindow : Window
    {
        private readonly TranslateTransform _interactiveTranslateTransform;
        public MainWindow()
        {
            InitializeComponent();

            _interactiveTranslateTransform = new TranslateTransform();

            _interactiveEllipse.RenderTransform =
                _interactiveTranslateTransform;

            _containerBorder.MouseLeftButtonDown +=
               border_mouseLeftButtonDown;
            _containerBorder.MouseRightButtonDown +=
                border_mouseRightButtonDown;
        }

        private void border_mouseLeftButtonDown(object sender, MouseButtonEventArgs e)
        {
            var clickPoint = Mouse.GetPosition(_containerBorder);

            // Set the target point so the center of the ellipse
            // ends up at the clicked point.
            var targetPoint = new Point
            {
                X = clickPoint.X - _interactiveEllipse.Width / 2,
                Y = clickPoint.Y - _interactiveEllipse.Height / 2
            };

            // Animate to the target point.
            var xAnimation =
                new DoubleAnimation(targetPoint.X,
                    new Duration(TimeSpan.FromSeconds(4)));
            _interactiveTranslateTransform.BeginAnimation(
                TranslateTransform.XProperty, xAnimation, HandoffBehavior.SnapshotAndReplace);

            var yAnimation =
                new DoubleAnimation(targetPoint.Y,
                    new Duration(TimeSpan.FromSeconds(4)));
            _interactiveTranslateTransform.BeginAnimation(
                TranslateTransform.YProperty, yAnimation, HandoffBehavior.SnapshotAndReplace);

            // Change the color of the ellipse.
            _interactiveEllipse.Fill = Brushes.Lime;
        }

        private void border_mouseRightButtonDown(object sender, MouseButtonEventArgs e)
        {
            // Find the point where the use clicked.
            var clickPoint = Mouse.GetPosition(_containerBorder);

            // Set the target point so the center of the ellipse
            // ends up at the clicked point.
            var targetPoint = new Point
            {
                X = clickPoint.X - _interactiveEllipse.Width / 2,
                Y = clickPoint.Y - _interactiveEllipse.Height / 2
            };


            // Animate to the target point.
            var xAnimation =
                new DoubleAnimation(targetPoint.X,
                    new Duration(TimeSpan.FromSeconds(4)));
            _interactiveTranslateTransform.BeginAnimation(
                TranslateTransform.XProperty, xAnimation, HandoffBehavior.Compose);

            var yAnimation =
                new DoubleAnimation(targetPoint.Y,
                    new Duration(TimeSpan.FromSeconds(4)));
            _interactiveTranslateTransform.BeginAnimation(
                TranslateTransform.YProperty, yAnimation, HandoffBehavior.Compose);

            // Change the color of the ellipse.
            _interactiveEllipse.Fill = Brushes.Orange;
        }
    }
}

实现效果:

实现效果

参考

1、
Microsoft Learn:培养开拓职业生涯新机遇的技能

2、
WPF-Samples/Animation/LocalAnimations/InteractiveAnimationExample.cs at main · microsoft/WPF-Samples (github.com)

前面我们使用了IIncrementalGenerator来生成代码,接下来我们来详细了解下IIncrementalGenerator的核心部分IncrementalValueProvider。

介绍

IncrementalValueProvider是基于管道的模式,将我们需要的数据进行处理转换后传递给SourceOutput。
目前官方提供可用的Providers有如下几种:

  • CompilationProvider
  • AdditionalTextsProvider
  • AnalyzerConfigOptionsProvider
  • MetadataReferencesProvider
  • ParseOptionsProvider

实操

接下来我们来使用AdditionalTextsProvider来学习IncrementalValueProvider的运行方式。

创建项目

首先创建LearnIncrementalValueProvider的控制台程序和LearnIncrementalValueProvider.Analysis的netstandard2.0类库两个项目。
image.png
按照前面HelloWorld项目的项目配置进行配置和引用。

添加LearnIncrementalValueProviderGenerator

在LearnIncrementalValueProvider.Analysis中添加LearnIncrementalValueProviderGenerator继承并实现IIncrementalGenerator接口。

using Microsoft.CodeAnalysis;
using System;
using System.Diagnostics;

namespace LearnIncrementalValueProvider.Analysis
{
    [Generator]
    public class LearnIncrementalValueProviderGenerator : IIncrementalGenerator
    {
        public void Initialize(IncrementalGeneratorInitializationContext context)
        {
            Debugger.Launch();
            var additionalTextsProvider = context.AdditionalTextsProvider;

            context.RegisterSourceOutput(additionalTextsProvider, (ctx, additionalTexts) =>
                                         {
                                             var path = additionalTexts.Path;
                                             var text = additionalTexts.GetText(ctx.CancellationToken);
                                         });
        }
    }
}

在实现的代码中,获取到AdditionalTextsProvider,并直接传递给RegisterSourceOutput,并在委托方法中直接获取AdditionalTextsProvider的文件路径以及文本内容。
在方法中加入Debugger.Launch();方便调试。

添加文件和调试

在控制台程序中,添加一个Files目录。往里面塞入一个swagger.json文件。
此时直接调试会发现,断点并不会进入到RegisterSourceOutput的委托中。
image.png
这是因为AdditionalTextsProvider并没有找到任何需要加载的文件。
我们需要在控制台程序的项目文件中添加AdditionalFiles,指定需要监听的文件。

<ItemGroup>
  <AdditionalFiles Include="Files/*" />
</ItemGroup>

添加AdditionalFiles后,在调试一次。
image.png
可以看到断点成功进来了。并且可以看到获取的文件路径以及文件的文本内容。
image.png

多个文件

在Files目录中添加一个txt文件。并写入文本HelloWorld
image.png
然后再调试一次。可以发现,每一个文件都会单独执行一次委托的方法。
image.png

过滤文件

当我们只需要其中一种类型的文件的时候,我们可以通过Where来进行过滤筛选。
image.png
通过Debugger.Log可以发现,只输出了json的文件路径。
image.png

处理数据

可以使用Select来处理我们的数据,比如这里我只获取文件名称。通过Debugger.Log可以看到输出了两个文件名称。
image.png

集合

如果不想多次处理文件的话,可以使用Collect方法,直接把多个文件合并在一起。
image.png
这里可以看到,使用Collect,2个文件可以同时处理。

组合多个IncrementalValueProvider

除了对单个IncrementalValueProvider进行处理外,我们还可以组合不同的IncrementalValueProvider。
比如将CompilationProvider和AdditionalTextsProvider组合起来。
使用Combine方法。
image.png
可以看到 paris的Right和Left分别是CompilationProvider和AdditionalTextsProvider两种类型。

结语

以上就是IncrementalValueProvider比较常用的方式。通过这些操作可以灵活的实现我们的代码生成逻辑。
当然还有其他的IncrementalValueProvider,这里就不都写出来了。其他的可以自己实操玩起来~
本文代码仓库地址https://github.com/fanslead/Learn-SourceGenerator

论文提出用于out-of-distributions输入检测的energy-based方案,通过非概率的energy score区分in-distribution数据和out-of-distribution数据。不同于softmax置信度,energy score能够对齐输入数据的密度,提升OOD检测的准确率,对算法的实际应用有很大的意义

来源:晓飞的算法工程笔记 公众号

论文: Energy-based Out-of-distribution Detection

Introduction


今天给大家分享一篇基于能量函数来区分非训练集相关(Out-of-distribution, OOD)输入的文章,连LeCun看了都说好。虽然文章是2020年的,但里面的内容对算法实际应用比较有用。这篇文章提出的能量模型想法在之前分享的
《OWOD:开放世界目标检测,更贴近现实的检测场景 | CVPR 2021 Oral》
也有应用,有兴趣的可以去看看。
现实世界是开放且未知的,OOD由于与训练集差异很大,使用通过特定训练集训练出来的模型进行预测的话,往往会出现不可控的结果。因此,确定输入是否为OOD并过滤掉,对算法在高安全要求场景下的应用是十分重要的。
大部分OOD研究依赖softmax置信度来过滤OOD输入,将低置信度的认定为OOD。然而,由于网络通常已经过拟合了输入空间,softmax对跟训练集差异较大的输入时常会不稳定地返回高置信度,所以softmax并不是OOD检测的最佳方法。还有部分OOD研究则从生成模型的角度来产生输入的似然分数
\(logp(x)\)
,但这种方法在实践中难以实现而且很不稳定,因为需要估计整个输入空间的归一化密度。
为此,论文提出energy-based方法来检测OOD输入,将输入映射为energy score,能直接应用到当前的网络中。论文还提供了理论证明和实验验证,表明这种energy-based方法比softmax-based和generative-based方法更优。

Background: Energy-based Models


EBM(energy-based model)的核心是建立一个函数
\(E(x): \mathbb{R}^D\to\mathbb{R}\)
,将输入
\(x\)
映射为一个叫energy的常量。
一组energy常量可以通过Gibbs分布转为概率分布
\(p(x)\)

这里将
\((x,y)\)
作为输入,对于分类场景,
\(E(x,y)\)
可认为是数据与标签相关的energy常量。分母
\(\int_{y^{'}}e^{-E(x,y^{'})/T}\)
是配分函数,即所有标签energy的整合,
\(T\)
是温度系数。
输入数据
\(x\in\mathbb{R}^D\)
的Helmholtz free energy
\(E(x)\)
可表示为配分函数的负对数:

结合公式1和公式2就构建了一个跟分类模型十分类似的EBM,可以通过Gibbs分布将多个energy输出转换为概率输出,还可以通过Helmholtz free energy得出最终的energy。
对于分类模型,分类器
\(f(x):\mathbb{R}^D\to\mathbb{R}^K\)
将输入映射为K个值(logits),随后通过softmax函数将其转换为类别分布:

其中
\(f_y(x)\)

\(f(x)\)
的第
\(y\)
个输出。

通过关联公式1和公式3,可在不改动网络
\(f(x)\)
的情况下将分类网络转换为EBM。定义输入
\((x,y)\)
的energy为softmax的对应输入值
\(E(x,y)=-f_y(x)\)
,再定义
\(x\in\mathbb{R}^D\)
的free energy为:

Energy-based Out-of-distribution Detection


Energy as Inference-time OOD Score

Out-of-distribution detection是个二分类问题,评价函数需要产生一个能够判定ID(in-distribution)数据和OOD(out-of-distribution)数据的分数。因此,论文尝试在分类模型上接入energy函数,通过energy进行OOD检测。energy较小的为ID数据,energy较大的为OOD数据。
实际上,通过负对数似然(negative log-likelihood,NLL))损失训练的模型本身就倾向于拉低ID数据的energy,负对数似然损失可表示为:

定义energy函数
\(E(x,y)=-f_y(x)\)
并将
\(log\)
里面的分数展开,NLL损失可转换为:

从损失值越低越好的优化角度看,公式6的第一项倾向于拉低目标类别
\(y\)
的energy,而公式6第二项从形式来看相当于输入数据的free energy。第二项导致整体损失函数倾向于拉低目标类别
\(y\)
的energy,同时拉高其它标签的energy,可以从梯度的角度进行解释:

上述式子是对两项的梯度进行整合,分为目标类别相关的梯度和非目标相关的梯度。可以看到,目标类别相关的梯度是倾向于更小的energy,而非目标类别相关的梯度由于前面有负号,所以是倾向于更大的energy。另外,由于energy近似为
\(-f_y(x)=E(x,y)\)
,通常都是目标类别的值比较大,所以NLL损失整体倾向于拉低ID数据的energy。

由于上述的energy特性,就可以基于energy函数
\(E(x;f)\)
进行OOD检测:

其中
\(\tau\)
为energy阈值,energy高于该阈值的被认定为OOD数据。在实际测试中,使用ID数据计算阈值,保证大部分的训练数据能被
\(g(x)\)
正确地区分。另外,需要注意的是,这里用了负energy分数
\(-E(x;f)\)
,是为了遵循正样本有更高分数的常规定义。

Energy Score vs. Softmax Score

论文先通过公式推导,来证明energy可以简单又高效地在任意训练好的模型上代替softmax置信度。将sofmax置信度进行对数展开,结合公式4以及
\(T=1\)
进行符号转换:

从上述式子可以看出,softmax置信度的对数实际上是free energy的特例,先将每个energy减去最大的energy进行偏移(shift),再进行free energy的计算,导致置信度与输入的概率密度不匹配。随着训练的进行,通常
\(f^{max}(x)\)
会变高,而
\(E(x; f)\)
则变低,所以softmax是有偏评价函数,置信度也不适用于OOD检测。

论文也通过真实的例子来进行对比,ID数据和OOD数据的softmax置信度差别很小(1.0 vs 0.99),而负energy则更有区分度(11.19 vs. 7.11)。因此,网络输出的值(energy)比偏移后的值(softmax score)包含更多有用的信息。

Energy-bounded Learning for OOD Detection

尽管energy score能够直接应用于训练好的模型,但ID数据和OOD数据的区分度可能还不够明显。为此,论文提出energy-bounded学习目标,对训练好的网络进行fine-tuned训练,显示地扩大ID数据和OOD数据之间的energy差异:

\(F(x)\)
为softmax输出,
\(D^{train}_{in}\)
为ID数据。整体的训练目标包含标准交叉熵损失,以及基于energy的正则损失:

\(D^{train}_{out}\)
为无标签的辅助OOD数据集,通过两个平方hinge损失对energy进行正则化,惩罚energy大于间隔参数
\(m_{in}\)
的ID数据以及energy小于间隔参数
\(m_{out}\)
的OOD数据。当模型fine-tuned好后,即可根据公式7进行OOD检测。

Experiment


ID数据集包含CIFA-10、CIFAR-100,并且分割训练集和测试集。OOD测试数据集包含Textures、SVHN、Places365、LSUN-Crop、LSUN_Resize和iSUN。辅助用的OOD数据集则采用80 Million Tiny Images,去掉CIFAR里面出现的类别。
评价指标采用以下:1)在ID数据95%正确的
\(\tau\)
阈值下的OOD数据错误率。2)ROC曲线下的区域大小(AUROC)。3)PR曲线下的区域大小(AUPR)。

从结果可以看出,energy score比softmax score的表现要好,而经过fine-tuned之后,错误就很低了。

与其他OOD方法进行比较。

可视化对比。

Conclustion


论文提出用于out-of-distributions输入检测的energy-based方案,通过非概率的energy score区分in-distribution数据和out-of-distribution数据。不同于softmax置信度,energy score能够对齐输入数据的密度,提升OOD检测的准确率,对算法的实际应用有很大的意义。



如果本文对你有帮助,麻烦点个赞或在看呗~
更多内容请关注 微信公众号【晓飞的算法工程笔记】

work-life balance.

蚁群算法

​ 蚁群算法由Marco Dorigo于1992年提出,该算法模拟了自然界中蚂蚁的觅食行为。蚂蚁在寻找食物源时,会在其经过的路径上释放一种信息素,并能够感知其他蚂蚁释放的信息素。信息素浓度的大小表征路径的远近,信息素浓度越高,表示对应的路径距离越短。通常蚂蚁会以较大的概率优先选择信息素浓度较高的路径,并释放一定量的信息素,以增强该条路径上的信息素浓度,这样,会形成一个正反馈。最终,蚂蚁能够找到一条从巢穴到食物源的最佳路径,即距离最短。生物学家发现,路径上的信息素浓度会随着时间的推进而逐渐衰减。

基本思路

​ 蚁群算法的基本思路为:用蚂蚁的行走路径表示待优化问题的可行解,整个蚂蚁群体的所有路径构成待优化问题的解空间。路径较短的蚂蚁释放的信息素量较多,随着时间的推进,较短的路径上累积的信息素浓度逐渐增高,选择该路径的蚂蚁个数也愈来愈多。最终,整个蚂蚁会在正反馈的作用下集中到最佳的路径上,此时对应的便是待优化问题的最优解。

蚁群算法的数学模型

​ 蚁群搜索食物的过程与TSP问题的求解过程非常相似,这里以TSP问题作为背景来介绍基本蚁群算法。所谓TSP问题就是求一条遍历所有n个城市且每个城市仅经过一次的最短路径。在ACO算法中,首先将m个蚂蚁随机分配到n个不同的城市中,通常m不大于n;然后m只蚂蚁同时由一个城市运动到另一个城市,逐步完成他们的搜索过程。蚂蚁k根据各个城市间的连接路径上的信息素浓度决定其访问的下一个城市,设$p_ij^k (t)$表示t时刻蚂蚁k从城市i转移到城市j的概率:

其中$τ_ij^α (t)$表示信息素浓度,它代表的是从i到j的后延效应;$η_ij^β (t)$为启发式信息,一般为启发式函数,它代表从i到j的先验效应。

启发式信息$η_ij$增加了对有潜力解的倾向性,它通常是与问题有关的独立函数。最小化路径长度问题的启发式信息:

​ η
ij
=1/d
ij

信息素浓度更新公式:

其中1-ρ表示信息素残留因子,∆τ
ij
k
表示第k只蚂蚁在城市i与城市j连接路径上释放的信息素浓度。

蚁群算法的三种模型

算法流程

​ 步骤1:初始化相关参数,如需遍历的城市数n、蚂蚁数m、初始时各路径信息素τ、m只蚂蚁遍历循环的次数最大值T
max
、信息素发挥p以及$\alpha$、$\beta$、Q等。建立禁忌列表J
k
,并保证此时表中未存任何城市信息。

​ 步骤2:将m只蚂蚁随机放在各个城市中,每个城市中至多分布一只蚂蚁;将m只蚂蚁所存在城市存入禁忌列表J
k

​ 步骤3:所有蚂蚁根据概率转换规则选择下一城市,并将选择城市存入禁忌列表。

​ 步骤4:所有蚂蚁遍历完n个城市后在所经过的路径上依据信息素更新公式更新信息素,并记录本次迭代过程中的最优路径和最优路径长度。

​ 步骤5:清空禁忌列表J
k
,重复步骤3和步骤4,直到每只蚂蚁均完成T
max
次遍历为止,最后输出的路径即为最优路径。

代码实例

%% 清空环境变量

clear all

clc

%% 导入数据

load citys_data.mat % 从名为 'citys_data.mat' 的文件中加载数据

%% 计算城市间的相互距离

n = size(citys,1); % 获取城市数量

D = zeros(n,n); % 创建一个用于存储城市间距离的零矩阵

for i = 1:n

​ for j = 1:n

​ if i ~= j

​ D(i,j) = sqrt(sum((citys(i,:) - citys(j,:)) .^ 2)); %勾股定理

​ else

​ D(i,j) = 1 * 10^-4; % 对角线上的距离设置一个很小的值,避免出现零值

​ end

​ end

end

%% 初始化参数

m = 50; %蚂蚁数量

alpha = 1; %信息素重要程度因子

beta = 5; %启发函数重要程度因子

rho = 0.1; %信息素挥发因子

Q = 1; %蚁周模型中的常系数

Eta = 1 ./ D; %启发函数

Tau = ones(n,n); %信息素矩阵,初始化为n行n列的全1方阵

Table = zeros(m,n); %路径记录表,m只蚂蚁所以有m行记录,每只蚂蚁经过n个城市的次序所以是n列

iter = 1; %迭代次数初值

iter_max = 200; %最大迭代次数

Route_best = zeros(iter_max,n); %各代最佳路径

Length_best = zeros(iter_max,1);%各代最佳路径的长度

Length_ave = zeros(iter_max,1); %各代路径的平均长度

%% 迭代寻找最佳路径

while iter <= iter_max

​ %随机产生各个蚂蚁的起点城市

​ start = zeros(m,1); % 创建一个初始城市编号的数组

​ for i = 1:m

​ temp = randperm(n); %把1到n这些数随机打乱得到的一个数字序列

​ start(i) = temp(1); %每只蚂蚁的起始位置是随机的

​ end

​ Table(:,1) = start; %路径记录表的第一列记为开始出发的城市

​ %构建解空间

​ citys_index = 1:n; %生成了一个1至31的一维数组

​ %逐个蚂蚁路径选择

​ for i = 1 : m

​ %逐个城市路径选择

​ for j = 2 : n

​ tabu = Table(i,1:(j - 1)); %已访问的城市集合(禁忌表)

​ allow_index = ~ismember(citys_index,tabu);

​ %找到尚未访问的城市,判断前一矩阵是否在后一矩阵中的逻辑值,并取反

​ allow = citys_index(allow_index); %待访问的城市集合

​ P = allow; % 创建概率数组,用于存储城市间转移概率

​ %计算城市间转移概率

​ for k = 1:length(allow)

​ P(k) = Tau(tabu(end),allow(k)) ^ alpha * Eta(tabu(end),allow(k)) ^ beta;

​ end

​ P = P / sum(P); % 归一化概率

​ %轮盘赌法选择下一个访问城市

​ Pc = cumsum(P);

​ target_index = find(Pc >= rand); % 选择满足条件的城市编号

​ target = allow(target_index(1)); % 获得下一个访问的城市编号

​ Table(i,j) = target; % 将下一个城市编号放入路径记录表

​ end

​ end

​ %计算各个蚂蚁的路径距离

​ Length = zeros(m,1); % 创建数组,用于存储各个蚂蚁的路径距离

​ for i = 1:m

​ Route = Table(i,:);

​ for j = 1:(n-1)

​ Length(i) = Length(i) + D(Route(j),Route(j+1));% 计算路径长度

​ end

​ Length(i) = Length(i) + D(Route(n),Route(1)); % 考虑最后一个城市回到起点的距离

​ end

​ %计算最短路径距离及平均距离

​ if iter == 1

​ [min_Length,min_index] = min(Length); % 获取最短路径长度及其索引(走出了最短路径的那只蚂蚁编号)

​ Length_best(iter) = min_Length; % 存储本次迭代中的最短路径长度

​ Length_ave(iter) = mean(Length); % 计算本次迭代产生所有值的平均路径长度

​ Route_best(iter,:) = Table(min_index); % 存储最佳路径

​ else

​ [min_Length,min_index] = min(Length); % 获取最短路径长度及其索引

​ Length_best(iter) = min(Length_best(iter - 1),min_Length);

​ % 更新最短路径长度,第一个参数是矩阵,第二个参数是标量,凡矩阵中的元素大于标量的,都用标量值替代

​ Length_ave(iter) = mean(Length); % 计算平均路径长度

​ if Length_best(iter) == min_Length

​ Route_best(iter,:) = Table(min_index,:); % 存储最佳路径

​ else


​ Route_best(iter,:) = Route_best((iter-1)

Spring Bean 的一生包括其从创建到消亡的整个过程:

实例创建 => 填充 => 初始化 => 使用 => 销毁。

这里需要注意的是,从 bean 实例的创建到可以使用之间还包括【填充】和【初始化】两个步骤。

AbstractAutowireCapableBeanFactory::createBean:bean 创建核心方法,包含创建、填充 bean 实例及应用 post-processors 等逻辑。

一、实例创建

1、实例化前置处理

InstantiationAwareBeanPostProcessor 为 BeanPostProcessor 子接口,用以提供【创建实例】前后回调处理。

如果有实现 InstantiationAwareBeanPostProcessor 接口,则应用此接口,返回结果如果不为 null,则直接返回作为 bean 实例。

2、doCreateBean

实际用于执行 bean 创建的方法,所有的创建、填充、初始化、注册销毁等逻辑都在此处处理。

BeanWrapper
:Spring 底层 JavaBean 结构核心接口,提供了分析和管理 JavaBean 的相关操作。不直接使用,通常隐式的通过 BeanFactory 或者 DataBinder 来使用。此处执行逻辑即为使用 BeanWrapper 对象。

factoryBeanInstanceCache
:存储 FactoryBean name --> BeanWrapper 键值映射。执行实例创建伊始,会先从 factoryBeanInstanceCache 查询获取,存在则直接获取(获取后删除)使用。

好吧,这里有个问题,为什么会有个 factoryBeanInstanceCache 缓存?

源头在于对单例 FactoryBean 类型操作,getSingletonFactoryBeanForTypeCheck。

创建 bean 实例 createBeanInstance:

优先级顺序:

  • 通过 InstanceSupplier 创建(5.0以后)

  • 通过工厂方法创建

  • 构造函数创建

至此,bean 实例已创建完毕。

此处还有一个 post-processor 处理:MergedBeanDefinitionPostProcessor,用于 bean 定义修改(只针对 RootBeanDefinition:merge 了多个来源 BeanDefinition 的运行时视图)。

3、单例实例提前暴露

为了解决单例循环依赖问题,提前将未完全创建好的单例实例缓存起来。

这里说的未完全创建好是指还不能正常使用。

earlySingletonExposure 条件:

  • 单例:scope 为 “singleton” 或者 ”“。

  • 允许自动处理循环依赖:allowCircularReferences 默认 true

  • 单例 bean 处于创建中:DefaultSingletonBeanRegistry:singletonsCurrentlyInCreation 存储所有处于创建中的 bean 名称。

addSingletonFactory:

将 singletonFactory 添加到 singletonFactories 缓存中,以备解决循环依赖使用。

singletonFactories 是什么呢?

字面意思为单例工厂缓存(bean name -> ObjectFactory ):即所谓的第三级缓存,存储目标 bean 所对应的 bean 工厂对象键值。

那 ObjectFactory 这个对象是怎么获取的呢?

SmartInstantiationAwareBeanPostProcessor::getEarlyBeanReference

SmartInstantiationAwareBeanPostProcessor 是 InstantiationAwareBeanPostProcessor 的扩展接口。

InstantiationAwareBeanPostProcessor 我们说过,是作用在创建实例前后。此处为创建实例后情景。

ObjectFactory 虽名为工厂,其实际为用以在 bean 创建早期,访问相应 bean 的一个引用。

什么是早期呢?

就是这会儿,刚创建完实例,还没有进行相应的填充、初始化等后续操作。

那为什么是暴露个引用,而不是直接给出目标对象呢?

因为目标 bean 可能还会经过其它 post-processors 处理。像 AbstractAutoProxyCreator::getEarlyBeanReference 中的代理逻辑处理。

二、填充

属性填充,作用于 AbstractAutowireCapableBeanFactory::populateBean。

1、属性填充前置处理

continueWithPropertyPopulation:是否继续处理属性填充判断。

这里的说明是在执行属性填充前给予任何 InstantiationAwareBeanPostProcessors 一个机会来变更 bean 的状态。

什么意思呢?

就是 InstantiationAwareBeanPostProcessors 的 postProcessAfterInstantiation 处理,对目标 bean 做相应的变更。

做什么变更呢?

这个节点在 Spring 自动注入操作之前,可以执行个性化的属性注入。同时,方法返回值会赋予 continueWithPropertyPopulation,以决定是否执行后续的逻辑。

这里有一个点需要注意:

如果当前 InstantiationAwareBeanPostProcessors::postProcessAfterInstantiation 返回 false,那么 bean 属性填充步骤则就此终止,不会再执行其它的 InstantiationAwareBeanPostProcessors 及后续的 Spring bean 属性填充过程。

2、属性填充

MutablePropertyValues

PropertyValues 接口的一个实现,提供对属性的各种操作,同时提供相应的构造函数来支持深度复制及基于 Map 的构造。

自动注入方式:按顺序 BY_NAME => BY_TYPE

BY_NAME

autowireByName 根据名称填充

填充什么呢?

unsatisfiedNonSimpleProperties。

什么是 unsatisfiedNonSimpleProperties 呢?

  • 可写的:即拥有写方法。

  • 需要依赖检查的:基于 ignoredDependencyTypes 属性设置判断。

  • 非本身类型的。

  • 非简单类型属性的:属性本身类型及数组元素类型为非简单类型。包括(基本类型及其包装类型,如 int、Integer 等)

注入:

首先根据属性名称判断 bean 存在:
即是否包含在 bean 工厂及外部注册单例 bean。

  • alias 的,会做相应的名称转换。

  • 存在继承关系的,会级联向上查询。

根据属性名称获取 bean:AbstractBeanFactory::getBean。

属性设置。

注册 bean 依赖:dependentBeanMap beanName -> Set<BeanName>,即记录 bean 及其依赖 bean 关系。

BY_TYPE

autowireByName 根据类型填充。

一个 BeanFactory 里必须恰好只有一个匹配需要类型。

同样,首先获取需要填充的属性:unsatisfiedNonSimpleProperties。

排除 Object 类型属性,填充没有意义。

处理依赖。

属性设置

注册 bean 依赖。

3、依赖检查

依赖检查分为两部分:一个基于 InstantiationAwareBeanPostProcessor::postProcessPropertyValues 处理。一个基于 AbstractBeanDefinition::dependencyCheck 处理。

InstantiationAwareBeanPostProcessor:

对特定的属性进行依赖检查及处理;对特定属性值进行替换,添加或者删除。

如 RequiredAnnotationBeanPostProcessor、 AutowiredAnnotationBeanPostProcessor、CommonAnnotationBeanPostProcessor、MockitoPostProcessor等。

dependencyCheck

检查所有暴露的属性是否都已赋值。

4、属性赋值

将上述处理过的属性值填充到 bean 实例。

三、初始化

应用工厂回调,定义的初始化方法及post-processors。

1、Aware 处理

Aware 代表了各种各样的资源,处理 Aware 即为将相应的资源添加到 bean 实例中。

如 BeanNameAware、BeanClassLoaderAware、BeanFactoryAware 等。

2、BeanPostProcessorsBeforeInitialization

顾名思义,这里的 BeanPostProcessors 是初始化之前的处理。

如 AbstractAdvisingBeanPostProcessor 检查。

3、执行初始化方法

a)实现了 InitializingBean 接口的 bean,执行相应的 afterPropertiesSet 方法。

b)定义了 initMethod 的,触发相应的方法调用。

两者是否可以同时存在呢?

可以,如果同时存在,但是初始化方法名称不能为 afterPropertiesSet。执行顺序为先 a 后 b。

4、BeanPostProcessorsAfterInitialization

同 2,此处为初始化之后的处理。

如 BeanValidationPostProcessor、ApplicationListenerDetector 等。

其实很多 PostProcessor 是既有 Before 处理逻辑,亦有 After 处理逻辑的,此处不再赘述。

四、disposable bean 注册

bean 工厂维护了一个 disposable bean 列表(bean name --> disposable instance)。在工厂关闭销毁时,同时销毁相应的 bean 实例对象。

定义销毁可以通过实现 DisposableBean 或者 AutoCloseable 接口或者自定义销毁方法。

如果使用一个定义了相应销毁方法的对象,又不想其执行销毁方法时怎么办呢?
注解或者配置其销毁方法为空,如:@Bean(destroyMethod = "")。

DestructionAwareBeanPostProcessor:实例销毁前,用户可以自定义执行特定的操作。如:ApplicationListenerDetector 移除相应的 Listener;ScheduledAnnotationBeanPostProcessor 移除定时任务等。