Brief History

• 1983, David Chaum first proposed to use encryption technology in digital cash
• 1998, Wei Dai’s B coin first introduced the idea of creating currency by solving calculation problems and decentralized consensus, but the proposal did not give a specific method to achieve decentralized consensus.
• 2005, Hal Finney introduced the concept of “reusable proof of work” (RPOW), which uses the idea of b-coin and the hash cash problem proposed by Adam Baker to create cryptology currency. However, this concept is once again lost in idealization because it relies on trusted computing as the back end.
• May/2007, Nakamoto Satoshi started the Bitcoin project
• August/2008, Nakamoto Satoshi registered domain name bitcoin.org
• 31/Obtober/2008, Nakamoto Satoshi sent an email to all members of a cryptography mailing list entitled “bitcoin: peer-to-peer e-cash thesis.”
• 16/November/2008, Nakamoto Satoshi announced the source code of bitcoin system
• 3/January/2009, Nakamoto Satoshi launched Bitcoin network on the Internet
• 22/May/2010, Bitcoin pizza Festival, one programmer traded 10,000 bitcoins for two great John pizza coupons. For the first time, bitcoin had a fair price: 10000 bitcoins cost $25
• November/2011, Nakamoto Satoshi disappeared

Why Bitcoin

1. Disintermediation: E-cash between individuals with no intervention of a trusted third-party intermediary
2. Decentralization: This e-cash currency issuance does not need a centralized institution, but is completed by the code and community consensus

Why dose Bit coin need Block Chain

In the digital world, if we want to create a disintermediated and decentralized “e-cash”, we also need to design a complete financial system.

This system should be able to solve a series of problems as follows:

• How can this “cash” be issued fairly and impartially without being controlled by any centralized institution or individual?
• How to realize that just like in the physical world, one person can hand the cash directly to another person without any intermediary assistance?
• How to “prevent counterfeiting” this kind of e-cash? Or how can an e-cash not be spent twice?

To solve the problems, Nakamoto developed Bitcoin system, which consists of 3 layers:

1. Application layer. The top layer is bitcoin. This is the application layer of the whole system.
2. Application protocol layer. The function of the middle layer is to issue bitcoin and handle the bitcoin transfer between users. This layer, also known as bitcoin protocol, is the application protocol layer of the whole system.
   1. Application layer. Transfer and bookkeeping functions
   2. Incentive layer. Issuance mechanism and distribution mechanism
   3. Consensus layer. POW(Proof Of Work)
3. General protocol layer. At the bottom are bitcoin’s distributed ledgers and decentralized networks. This layer, also known as bitcoin blockchain, is the general protocol layer of the whole system.
   1. Network layer. P2P mechanism, broadcast mechanism, and verification mechanism
   2. Data layer. Block data(Hash), chain structure(Merkle Tree), and digital signature(Asymmetric encryption)

In the design of bitcoin system, Nakamoto creatively combines computer computing power competition with economic incentives to form a proof of work (POW) consensus mechanism, which enables mining computer nodes to complete the function of currency issuance and accounting in the calculation competition, as well as the operation and maintenance of blockchain ledger and decentralized network.

This forms a complete cycle: the mining machine mining (calculation power competition), the completion of decentralized accounting (operation system), and the economic incentive (economic reward) in the form of bitcoin.

Bitcoin’s workload proof consensus mechanism is a connecting layer, connecting the upper application and the lower technology: the upper layer is the issuance, transfer and anti-counterfeiting of e-cash; the lower layer is the node to the central network to reach an agreement and update the distributed ledger.

Definition of Blockchain

Blockchain is the technology of “value representation” and “value transfer” in the digital world. One side of blockchain coin is the encrypted digital currency or token representing value, and the other side is the distributed ledger and decentralized network for value transfer.

Blockchain is an underlying technology derived from bitcoin. In other words, bitcoin is the first successful application of blockchain technology.

When people talk about Blockchain, what do they mean:

1. Blockchain refers to the data structure of bitcoin, that is, the chain formed by the connection of data blocks, which is also known as “distributed ledger”. In the bitcoin white paper, Nakamoto mentioned block and chain respectively, but later they were combined into the new term block chain.
2. Blockchain refers to the combination of bitcoin’s distributed ledger and decentralized network. Corresponding to bitcoin system, it refers to the whole third layer of bitcoin blockchain.
3. Blockchain refers to the combination of the second layer (bitcoin protocol) and the third layer (bitcoin blockchain) of bitcoin system. It includes distributed ledgers, decentralized networks and bitcoin protocols.
4. Blockchain refers to the whole bitcoin system, including all three layers, including bitcoin with value representation and the whole system behind it. From this perspective, blockchain is regarded as a complete system including both technical and economic parts.

When referring to blockchain, ordinary people often refers to the fourth largest scope, namely “account book + Network + protocol + currency”. In the industry, when people refer to blockchain, they usually refer to the third scope, namely “account book + Network + Protocol”. When talking about blockchain, many software developers usually refer to the second range of “ledger + network”.

reference:
http://c.biancheng.net/view/1884.html

An evaluation index system refers to an organic whole with an internal structure composed of multiple indicators that characterize various aspects of the evaluation object and their interconnections.

Principles to be followed

In order to make the indicator system scientific and standardized, the following principles should be followed when constructing it:

1. Systematic principle. There should be a certain logical relationship between the indicators. They should not only reflect the main characteristics and states of the ecological, economic and social subsystems from different aspects, but also reflect the internal relationship between the ecological, economic and social systems. Each subsystem is composed of a set of indicators, which are independent of each other and connected with each other to form an organic unity. The construction of the index system is hierarchical, from the top to the bottom, from the macro level to the micro level, forming an indivisible evaluation system.
2. Typical principle. It is necessary to ensure that the evaluation indicators have certain typical representativeness, and reflect the comprehensive characteristics of the environment, economy and social changes in a specific region as accurately as possible. Even if the number of indicators is reduced, it is also necessary to facilitate data calculation and improve the reliability of the results. In addition, the setting of evaluation index system, the distribution of weight among indexes and the division of evaluation standard should be adapted to the natural and socio-economic conditions of a specific region.
3. Dynamic principle. The interactive development of ecology, economy and social benefits can only be reflected through certain time scale indicators. Therefore, dynamic changes should be fully considered in the selection of indicators, and the change values of several years should be collected.
4. Concise and scientific principle. The design of each index system and the selection of evaluation indexes must be based on the principle of scientificity, which can objectively and truly reflect the characteristics and conditions of Gaoxigou’s environmental, economic and social development, and can objectively and comprehensively reflect the real relationship between each index. Each evaluation index should be typical, not too many and too detailed, so that the index is too cumbersome and overlapping, and the index cannot be too few and too simple, so as to avoid the omission of index information, errors and untrue phenomena, and the data is easy to obtain and the calculation method is simple and easy to understand.
5. Comparable, operable and quantifiable principle. In terms of indicator selection, special attention should be paid to the consistency within the overall scope. The construction of indicator system serves for the formulation of field assessment and scientific management. The calculation measures and calculation methods of indicator selection must be consistent and unified. Each indicator should be as simple and clear as possible, micro and easy to collect. Each indicator should be highly practical, operable and comparable. In addition, when selecting indicators, it is also necessary to consider whether quantitative processing can be carried out to facilitate mathematical calculation and analysis.
6. Comprehensive principle. At the corresponding evaluation level, the factors affecting the environment, economy and social system are comprehensively considered, and comprehensive analysis and evaluation are carried out.

Features that should be possessed

And the constructed index system should possess these features:

1. Perform a clear guidance direction
2. Quantitative based and qualitative supplemented
3. Difference classification considered

General construction process

1. Building the theoretical foundation
2. Provide empirical evidence
   1. Statistical data support
   2. Evidence from typical cases
   3. Reasonable interpretation of contradictory cases
3. Verify operability

Representative evaluation system: 3E

3E theory refers to:

• Efficacy, which measures its own output
• Efficiency, which reflects the utilization of resources
• Effectiveness, which reflects the effect of the system output on its superior system

3E system represents the trend of diversified development of performance evaluation system. Through the establishment of 3E standard system, the soft environment evaluation system is more scientific and transparent, and the efficiency and operability of performance evaluation are increased, which greatly promotes the improvement and development of public policy evaluation system.

reference:
https://www.researchgate.net/profile/Francisco_Ruiz14/publication/220831115_Quality_Assessment_of_Business_Process_Models_Based_on_Thresholds/links/5473100f0cf216f8cfae97f4.pdf
author:
Laura Sánchez-González, Félix García, Jan Mendling, Francisco Ruiz
Institution:
Grupo Alarcos, Universidad de Castilla La Mancha
Humboldt-Universität zu Berlin

Background and Motivation

Process improvement is recognized as the main benefit of process modelling initiatives. Quality considerations are important when conducting a process modelling project. While the early stage of business process design might not be the most expensive ones, they tend to have the highest impact on the benefits and costs of the implemented business processes. In this context, quality assurance of the models has become a significant objective.

Quality from the perspective of understandability and modifiability

The aim of our empirical research approach is to validate the connections between an extensive set of metrics (number of nodes, diameter, density, coefficient of connectivity, average gateway degree, maximum gateway degree, separability, sequentiality, depth, gateway mismatch, gateway heterogeneity, cyclicity and concurrency) and the ease with which business process models can be understood (understandability) and modified (modifiability).

null hypothesis: There is no correlation between structural metrics and understandability and modifiability

The structural metrics apparently seem to be closely connected with understandability and modifiability.

1. For understandability these include Number of Nodes, Gateway Mismatch, Depth, Coefficient of Connectivity and Sequentiality.
2. For modifiability Gateway Mismatch, Density and Sequentiality showed the best results.

Conclusion

After analyzing which measures are most useful, it is interesting to know what values of these measures indicate poor quality in models. That means, thresholds values could be used as an alarm of detecting low-quality structures in conceptual models.

The strength of the correlation of structural metrics with different quality aspects clearly shows the potential of these metrics to accurately capture aspects closely connected with actual usage.

写年度报告也好，写普通报告也好，如果能够掌握一些技巧的话，就可以给自己的报告增色不少。

绝对值，相对化

有一些数据，直接拿出来并不好看。然而如果把这些绝对值转化成相对值，比如百分比、环比、增长率等，事情就大不一样。

例子：

相对值，模糊化

有的数据已经不错了，但是老板总觉得不够好。这个时候，就需要把这些数据进行模糊化。

例子

模糊值，整合化

汇报的时候，老板通常会更在意比较“差”的部分，而这些也会直接影响你的最终评估结果。但是一年发生了这么多事情，不可能事事顺心，都表现的很好。因此需要把分散的值，整合起来。

例子：

整合值，定语化

有些时候，无论怎么整合，这些数据就是不好看。这个时候，需要在报告的数据前边加上定语，对数据进行过滤。

例子：

结语：

无论怎么套路，没做就是没做，多少就是多少，实事求是不扯谎，这是底线。

本文只是给大家提供一些年度报告的包装思路，往坏了说算是歪门邪道，充其量可以帮助大家临时抱抱佛脚。

巧妇难为无米之炊，最重要的还是平时下足功夫。把工作做好，对自己、对别人都是负责。

多一些真诚，少一些套路。

reference:
https://e-archivo.uc3m.es/bitstream/handle/10016/27943/how_MOBICOM_2018_ps.pdf?sequence=1
author:
Cristina Marquez, Marco Gramaglia, Marco Fiore, Alert Banchs, Xavier Costa-Perez
Institution:
Universidad Carlos III Madrid
CNR-IEIIT (Institute of Electronics, Computer and Telecommunication Engineering, the National Research Council of Italy)
NEC Laboratories Europe

FOR A QUICK GLANCE

What is network slicing or background

Network slicing has profound implications on resource management, as it entails an inherent trade-off between:

(i) the need for fully dedicated resources to support service customization, and

(ii) the dynamic resource sharing among services to increase resource efficiency and cost-effectiveness of the system.

Why study it or what is the problem

While the technology needed to support this paradigm is well understood from a system standpoint, its implications in terms of efficiency are still unclear.

How to do

In this paper, we fill such a gap via an empirical study of resource management efficiency in network slicing.

Building on substantial measurement data collected in an operational mobile network

(i) we quantify the efficiency gap introduced by non-reconfigurable allocation strategies of different kinds of resources, from radio access to the core of the network, and

(ii) we quantify the advantages of their dynamic orchestration at different timescales.

As a result

Our results provide insights on the achievable efficiency of network slicing architectures, their dimensioning, and their interplay with resource management algorithms.

INTRODUCTION

Background

Current trends in mobile networks point towards a strong diversification of services, which are characterized by increasingly heterogeneous Key Performance Indicator (KPI) and Quality of Service (QoS) requirements.

current mobile network architectures lack the necessary flexibility to meet the ex- treme requirements imposed by such services.

Network virtualization and slicing

The agenda for 5G networks is to achieve this mainly via network virtualization, which evolves the traditional hardbox paradigm into a cloudified architecture where the once hardware-based network functions are implemented as software Virtual Network Functions (VNFs) running on a general-purpose telco-cloud. Network virtualization enables the deployment of multiple virtual instances of the complete network, named network slices.

Network slicing strategies. Deeper slices (A to E) reserve resources to services across a wider portion of the end-to-end network architecture, but reduce the space for unconstrained resource sharing.

Network slicing and resource management

When instantiating a slice, an operator needs to allocate sufficient computational and communication resources to its VNFs. In some cases, these resources may be dedicated, be- coming inaccessible to other slices. Alternatively,

Inherent trade-off

(i) service customization, which favours the deployment of specialized slices with tailored functions for each service and, possibly, dedicated and guaranteed resources;

(ii) resource management efficiency, which increases by dynamically shar- ing the resources of the common infrastructure among the different services and slices; and,

(iii) system complexity, resulting from deploying more dynamic resource allocation mechanisms that provide higher efficiency at the cost of em- ploying elaborate operation and maintenance functions.

Contribution of this paper

From a system standpoint, the technology needed to support the different types of slices is well understood or even already available.

Our aim is to shed light on the trade-offs between customization, efficiency, and complexity in network slicing, by evaluating the impact of resource allocation dynamics at different network points. Based on our analysis, it is thus possible to determine in which cases the gains in efficiency are worth the sacrifice in customization/isolation and/or the extra complexity. Since resource management efficiency in network slicing highly depends on the traffic patterns of different services supported by the various slices, we build on substantial service-level measurement data collected by a major operator in a production mobile network, and:

(i) quantify the price paid in efficiency when suitable algorithms for dynamic resource allocation are not available, and the operator has to resort to physical network duplication;

(ii) evaluate the impact of sharing resources at different
locations of the network, including the cloudified core, the virtualized radio access, or the individual antennas;

(iii) outline the benefit of dynamic resource allocation
at different timescales, i.e., allowing to reallocate resources across slices with different reconfiguration intervals

NETWORK SCENARIO AND METRICS

Network slicing scenario

The operator owning the infrastructure implements slices $s \in S$ , each dedicated to a different subset of services. Every network level $\ell$ is composed by a set $C_{\ell}$ of network nodes.

model the mobile network architecture as a hierarchy composed by a fixed number of levels ( $\ell=1, \ldots, L$ ) ordered from the most distributed ( $\ell=1$ ) to the most centralized ( $\ell=L$ )

Slice specifications

Denote a slice specification as:

$$
\mathbb{Z}=(f, w)
$$

involves:

(i) Guaranteed time fraction $f$ : the operator engages to guarantee that the traffic demand of the slice is fully serviced during at least a fraction $f \in[0,1]$ of time.

(ii) Averaging window length w: the operator commitment on fraction f above is intended on discrete-time demands of granularity w, with traffic averaged over the disjoint time windows of duration w.

average load over window k covering a time interval of the same name with duration w:

$$
\bar{o} _ {c,s} (k)=\frac{1}{w}\int_{k}o_{c, s}(t)\mathrm{d}t
$$

the amount of resources allocated to slice s at node c during window k:

$$
r_{c, s}^{\mathbb{Z}}(k)
$$

Resource allocation to slices

Let $F _ {s, c, n} ^ {w}$ be the Cumulative Distribution Function (CDF)
of the demand for slice s at node c during reconfiguration period k, averaged over windows of length w: then, the minimum $\hat{r} _ {c, s} ^ {\mathbb{Z}} (n)$
that satisfies Equation (1) can be computed as $\hat{r} _ {c, s} ^ {\mathbb{Z}} (n)=\left(F_{s, c, n}^{w}\right)^{-1}(f)$ .

$$
\mathbb{R} _ {\ell, \tau} ^ {\mathbb{Z}} = \sum _ {s \in \mathcal{S}} \sum _ {\mathcal{C} \in C _ {\ell}} \sum_{n \in \mathcal{T}} \tau \cdot \hat{r} _ {c, s} ^ {\mathbb{Z}} (n)
$$

The above equation represents the total amount of resources needed to meet slice specifications, under the possibility of dynamically re-configuring the allocation with periodicity $\tau$ .

Multiplexing efficiency

In perfect sharing, the allocated resources correspond to those required when there is no isolation among different services, hence traffic multiplexing is maximum. Formally,

$$
\mathbb{P} _ {\ell, \tau} ^ {\mathbb{Z}} = \sum _ {c \in C_{\ell}} \sum _ {n \in \mathcal{T}} \tau \cdot \hat{r} _ {c} ^ {\mathbb{Z}} (n)
$$

Multiplexing efficiency as the ratio between the resources required with network slicing and those needed under perfect sharing:

$$
\mathbb{B} _ {\ell, \tau} ^ {\mathbb{Z}} = \mathbb{R} _ {\ell, \tau} ^ {\mathbb{Z}} / \mathbb{P} _ {\ell, \tau} ^ {\mathbb{Z}}
$$

CASE STUDIES

Our two reference urban regions are a large metropolis of
several millions of inhabitants, and a typical medium-sized city with a population of around 500,000, both situated in Europe. Service-level measurement data was collected in the target areas by a major operator with a national market share of around 30%. We leverage these real-world traffic demands to define network slices. Details are in Section 3.1.

On top of this, we model the hierarchical network infrastructures in the target regions by assuming that the operator deploys level- $\ell$ nodes so as to balance the offered load among them. This is discussed in Section 3.2.

DATA-DRIVEN EVALUATION

We organise our evaluation as follows. First, we investigate worst-case settings where very stringent slice specifications are enforced, and no dynamic reconfiguration of resources is possible (Section 4.1). We then relax these constraints, and assess efficiency as slice specifications are softened (Section 4.2), or in presence of periodic resource orchestration (Section 4.3). Finally, we evaluate the impact of varied slice configurations (Section 4.4), and of a resource assignment accounting for instantaneous traffic demands (Section 4.5).

TAKEAWAYS AND PERSPECTIVES

1. Multi-service requires more resources
2. Traffic direction is a factor
3. Loose service level agreements may not help
4. Dynamic resource assignment must also be rapid
5. Aggregating services is beneficial
6. Deployment is slightly more efficient than operation
7. Urban topography has limited impact
8. There is room for improvement

Just use:

1

pip install PyExecJS

or

1

pip3 install PyExecJS

写给自己：

1. 不管别人有没有催，不管有没有投稿日，都要给自己一个deadline
2. 想法不成熟也没关系，方法有瑕疵也没关系，总之先开始写，把想到的东西都写下来
3. 整理出第一版，就算再烂，也比没有强
4. 拿着写好内容，再去找各路大神讨论，不断优化，事半功倍

图例

说明

多目标优化是多准则决策的一个领域，它是涉及多个目标函数同时优化的数学问题。多目标优化已经应用于许多科学领域，包括工程、经济和物流，其中需要在两个或多个相互冲突的目标之间进行权衡的情况下作出最优决策。分别涉及两个和三个目标的多目标优化问题的例子有：在购买汽车时降低成本，同时使舒适性最大化；在使车辆的燃料消耗和污染物排放最小化的同时将性能最大化。在实际问题中，甚至可以有三多个目标。

对于非平凡多目标优化问题，不存在同时优化每个目标的单个解决方案。在这种情况下，目标函数被说成是冲突的，并且存在一个（可能无限）数量的帕累托最优解。如果目标函数在值上不能改进而不降低其他一些目标值，则解决方案称为非支配、Pareto最优、Pareto有效或非劣解。如果没有额外的主观偏好信息，所有Pareto最优解都被认为是同样好的（因为向量不能完全排序）。研究人员从不同的角度研究多目标优化问题，从而在设置和解决多目标优化问题时存在不同的求解哲学和目标。目标可以是找到帕累托最优解的代表性集合，and/or量化满足不同目标的折衷，and/or找到满足人类决策者decision maker(DM)的主观偏好的单一解决方案。

形式化定义

$$
\begin{array}{cl}{\min / \max } & {f_{m}(x), \quad m=1,2, \ldots, M} \\ {\text { subject to }} & {g_{j}(x) \geq 0, \quad j=1,2, \ldots, J} \\ {} & {h_{k}(x)=0, \quad k=1,2, \ldots, K} \\ {} & {x_{i}^{(Lower)} \leq x_{i} \leq x_{i}^{(Upper)}, \quad i=1,2, \ldots, n} \end{array}
$$

发展历史

多目标优化算法归结起来有传统优化算法和智能优化算法两大类。

1. 传统优化算法包括加权法、约束法和线性规划法等，实质上就是将多目标函数转化为单目标函数，通过采用单目标优化的方法达到对多目标函数的求解。
2. 智能优化算法包括进化算法（Evolutionary Algorithm, 简称EA）、粒子群算法（Particle Swarm Optimization, PSO）等。

从九十年代初开始，进化算法系列算法被统一，如遗传算法等。

多目标优化问题的解

在单目标优化问题中，通常最优解只有一个，而且能用比较简单和常用的数学方法求出其最优解。然而在多目标优化问题中，各个目标之间相互制约，可能使得一个目标性能的改善往往是以损失其它目标性能为代价，不可能存在一个使所有目标性能都达到最优的解，所以对于多目标优化问题，其解通常是一个非劣解的集合——Pareto解集。

帕累托最优（Pareto Optimal）：帕雷托最优是指资源分配的一种理想状态。给定固有的一群人和可分配的资源，如果从一种分配状态到另一种状态的变化中，在没有使任何人境况变坏的前提下，使得至少一个人变得更好，这就是帕雷托改善。帕雷托最优的状态就是不可能再有更多的帕雷托改善的状态；换句话说，不可能在不使任何其他人受损的情况下再改善某些人的境况。帕累托最优解集的边界（boundary）被称为帕累托最优前沿面（Pareto-optimal front）。

在存在多个Pareto最优解的情况下，如果没有关于问题的更多的信息，那么很难选择哪个解更可取，因此所有的Pareto最优解都可以被认为是同等重要的。由此可知，对于多目标优化问题，最重要的任务是找到尽可能多的关于该优化问题的Pareto最优解。因而，在多目标优化中主要完成以下两个任务：

1. 找到一组尽可能接近Pareto最优域的解。
2. 找到一组尽可能不同的解。

第一个任务是在任何优化工作中都必须的做到的，收敛不到接近真正Pareto最优解集的解是不可取的，只有当一组解收敛到接近真正Pareto最优解，才能确保该组解近似最优的这一特性。

几种常用的多目标优化问题解决方法

Weighted Sum Method

线性加权法，其中权重代表了每个目标函数的重要程度。

$$
\begin{array}{rl}{\min } & {F(x)=\sum_{m=1}^{M} w_{m} f_{m}(x)} \\ {\text { subject to }} & {g_{j}(x) \geq 0, \quad j=1,2, \ldots, J} \\ {} & {h_{k}(x)=0, \quad k=1,2, \ldots, K} \\ {} & {x_{i}^{(Lower)} \leq x_{i} \leq x_{i}^{(Upper)}, \quad i=1,2, \ldots, n}\end{array}
$$

优点：简单

缺点：很难设定一个权重向量能够去获得帕累托最优解；在一些非凸情况不能够保证获得帕累托最优解

$\varepsilon$ -constraint method

只保留一个目标函数，其他的目标函数被设定的值约束。

$$
\begin{array}{cl}{\min } & {f_{\mu}(x)} \\ {\text {subject to }} & {f_{m}(x) \leq \epsilon_{m}, \quad m=1,2, \ldots, M \text { and } m \neq \mu} \\ {} & {g_{j}(x) \geq 0, \quad j=1,2, \ldots, J} \\ {} & {h_{k}(x)=0,} \quad {k=1,2, \ldots, K} \\ {} & {x_{i}^{(Lower)} \leq x_{i} \leq x_{i}^{(Upper)},} \quad {i=1,2, \ldots, n}\end{array}
$$

优点：能够应用到凸函数和非凸函数场景下

缺点：函数需要精心选择；需要在独立目标函数的最小值或最大值之内

Weighted Metric Method

$$
\begin{array}{cl}{\min } & {l_{p}(x)=\left(\sum_{m=1}^{M} w_{m}\left|f_{m}(x)-z_{m}^{*}\right|\right)^{1 / p}} \\ {\text { subject to }} & {g_{j}(x) \geq 0, \quad j=1,2, \ldots, J} \\ {} & {h_{k}(x)=0, \quad k=1,2, \ldots, K} \\ {} & {x_{i}^{(Lower)} \leq x_{i} \leq x_{i}^{(Upper)}, \quad i=1,2, \ldots, n}\end{array}
$$

优点：weighted Techebycheff metirc能够保证获得所有帕累托最优解

缺点：需要有每个函数最大值和最小值的先验知识；需要每个目标函数的 $z^{*}$ 能够独立被找到；对于较小的p值，不一定保证所有能够获得所有帕累托最优解；随着p增加，问题会变得不可求导

Multi-Objective Genetic Algorithms

基于遗传算法的多目标优化就是利用遗传算法的原理来搜索帕累托最优前沿面。

遗传算法相比与传统算法的优点是能够得到一个最优解集，而不是单单一个最优解，这样给我们更多的选择。但计算复杂度可能稍高，而且里面涉及的一些函数需要精心设计。

详见：https://imonce.github.io/2019/11/07/启发式算法学习（三）：遗传算法/

发展分析

多目标优化算法相对成熟，在不同的问题使用不同的优化算法。NSGA-II, SPEA 或者 MOPSO都是可选项，而到底选择哪一个方法，还需要根据特定的情景选择。

尽管多目标优化算法应用于动态的制造系统，dynamic manufacturing systems，但是制造系统和很复杂的，并且是动态的，因此算法还是有一定的缺陷性。

未来发展方向：

1. 因为多种多目标方法已经被提出，混合方法 hybrid method可以被进一步发展。

2. 现在的动态制造系统中的多目标优化算法需要动态调度的能力

Reference:
https://www.jiqizhixin.com/graph/technologies/cf8932be-519a-4fd9-84f9-c6ffa997a554
https://blog.csdn.net/paulfeng20171114/article/details/82454310
https://hpzhao.github.io/2018/09/17/多目标优化四种方法/
https://zh.wikipedia.org/wiki/帕累托最优

算法简介

蚁群算法（Ant Colony Algorithm, AG, or Ant Colony Optimization, ACO），又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型算法。它由Marco Dorigo于1992年在他的博士论文“Ant system: optimization by a colony of cooperating agents”中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。蚁群算法是一种模拟进化算法，初步的研究表明该算法具有许多优良的性质。针对PID控制器参数优化设计问题，将蚁群算法设计的结果与遗传算法设计的结果进行了比较，数值仿真结果表明，蚁群算法具有一种新的模拟进化优化方法的有效性和应用价值。

基本原理

蚂蚁会在其经过的路径上释放一种可以称之为“信息素”的物质，蚁群内的蚂蚁对“信息素”具有感知能力，它们会沿着“信息素”浓度较高路径行走，而每只路过的蚂蚁都会在路上留下“信息素”，这就形成一种类似正反馈的机制，这样经过一段时间后，整个蚁群就会沿着最短路径到达食物源了。可以分解为以下几步：

1. 蚂蚁在路径上释放信息素。
2. 碰到还没走过的路口，就随机挑选一条路走。同时，释放与路径长度有关的信息素。
3. 信息素浓度与路径长度成反比。后来的蚂蚁再次碰到该路口时，就选择信息素浓度较高路径。
4. 最优路径上的信息素浓度越来越大。
5. 最终蚁群找到最优寻食路径。

算法流程

蚁群算法解决旅行商问题的流程：

数学模型

这个利用TSP问题来说明这个数学模型，对于TSP问题，设蚂蚁群体中蚂蚁的数量为m，城市的数量为n，城市i与城市j之间的距离为 $d_{ij}$ ，t时刻城市i与城市j连接路径上的信息素浓度为 $c_{ij}(t)$ 。初始时刻，蚂蚁被放置在不同的城市里，且各城市键连接路径上的信息素浓度相同。然后蚂蚁将按一定概率选择线路，不放设 $p^k_{ij}(t)$ 为t时刻蚂蚁k从城市i转移到城市j的概率。“蚂蚁TSP”策略收到两方面的左右，首先是访问某城市的期望，领完便是其他蚂蚁释放的信息素浓度。所以已定义：

$$p_{ij}^{k}(t)=\left\lbrace\begin{array}{cll}
\frac{[c_{ij}(t)]^{a} * [n_{ij}(t)]^{b}}{\sum [c_{ij}(t)]^{a} * [n_{ij}(t)]^{b}} & , & j \in allowk \\
0 & , & j \notin allowk
\end{array}\right.$$

其中：

• $n_{ij}(t)$ 为启发函数，表示蚂蚁从城市i转移到城市j的期望
• $allowk$ 为蚂蚁带访问城市集合，开始时， $allowk$ 中有 $n−1$ 个元素，即包括除了蚂蚁k出发城市的其他多个城市，随着时间的推移， $allowk$ 中的元素越来越少，直至为空
• $a$ 为信息素重要程度因子
• $b$ 为启发函数因子

在蚂蚁遍历各城市的过程中，与实际情况相似的是，在蚂蚁释放信息素的同事，各个城市之间连接路径上的信息素的强度也在通过挥发等方式逐渐消失。为了描述这个特征，设ρ表示信息素挥发程度。这样所有蚂蚁完成走完一遍所有城市之后，各个城市键连接路径上的信息素浓度为

$$c_{ij}(t+1) = (1-\rho)*c_{ij}(t) + \Delta c_{ij}$$

$$\Delta c_{ij} = \sum \Delta c^k_{ij}$$

$\Delta c^k_{ij}$ 为第k只蚂蚁在城市i与城市j连接路径上释放信息素而增加的信息素浓度。

$\Delta c_{ij}$ 为所有蚂蚁在城市i与城市j连接路径上释放信息素而增加的信息素浓度。

一般情况下 $\Delta c^k_{ij}=\frac{Q}{L_k}$ ,若蚂蚁k从城市i访问了城市j，其中 $Q$ 为信息素常数， $L_k$ 为第k只蚂蚁经过路径总长度。

python代码

代码来源：https://blog.csdn.net/fanxin_i/article/details/80380733

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325

# -*- coding: utf-8 -*-
import random
import copy
import time
import sys
import math
import tkinter #//GUI模块
import threading
from functools import reduce
 
 
# 参数
'''
ALPHA:信息启发因子，值越大，则蚂蚁选择之前走过的路径可能性就越大
      ，值越小，则蚁群搜索范围就会减少，容易陷入局部最优
BETA:Beta值越大，蚁群越就容易选择局部较短路径，这时算法收敛速度会
     加快，但是随机性不高，容易得到局部的相对最优
'''
(ALPHA, BETA, RHO, Q) = (1.0,2.0,0.5,100.0)
# 城市数，蚁群
(city_num, ant_num) = (50,50)
distance_x = [
    178,272,176,171,650,499,267,703,408,437,491,74,532,
    416,626,42,271,359,163,508,229,576,147,560,35,714,
    757,517,64,314,675,690,391,628,87,240,705,699,258,
    428,614,36,360,482,666,597,209,201,492,294]
distance_y = [
    170,395,198,151,242,556,57,401,305,421,267,105,525,
    381,244,330,395,169,141,380,153,442,528,329,232,48,
    498,265,343,120,165,50,433,63,491,275,348,222,288,
    490,213,524,244,114,104,552,70,425,227,331]
#城市距离和信息素
distance_graph = [ [0.0 for col in range(city_num)] for raw in range(city_num)]
pheromone_graph = [ [1.0 for col in range(city_num)] for raw in range(city_num)]
 
 
 
#----------- 蚂蚁 -----------
class Ant(object):
 
    # 初始化
    def __init__(self,ID):
        
        self.ID = ID                 # ID
        self.__clean_data()          # 随机初始化出生点
 
    # 初始数据
    def __clean_data(self):
    
        self.path = []               # 当前蚂蚁的路径           
        self.total_distance = 0.0    # 当前路径的总距离
        self.move_count = 0          # 移动次数
        self.current_city = -1       # 当前停留的城市
        self.open_table_city = [True for i in range(city_num)] # 探索城市的状态
        
        city_index = random.randint(0,city_num-1) # 随机初始出生点
        self.current_city = city_index
        self.path.append(city_index)
        self.open_table_city[city_index] = False
        self.move_count = 1
    
    # 选择下一个城市
    def __choice_next_city(self):
        
        next_city = -1
        select_citys_prob = [0.0 for i in range(city_num)]  #存储去下个城市的概率
        total_prob = 0.0
 
        # 获取去下一个城市的概率
        for i in range(city_num):
            if self.open_table_city[i]:
                try :
                    # 计算概率：与信息素浓度成正比，与距离成反比
                    select_citys_prob[i] = pow(pheromone_graph[self.current_city][i], ALPHA) * pow((1.0/distance_graph[self.current_city][i]), BETA)
                    total_prob += select_citys_prob[i]
                except ZeroDivisionError as e:
                    print ('Ant ID: {ID}, current city: {current}, target city: {target}'.format(ID = self.ID, current = self.current_city, target = i))
                    sys.exit(1)
        
        # 轮盘选择城市
        if total_prob > 0.0:
            # 产生一个随机概率,0.0-total_prob
            temp_prob = random.uniform(0.0, total_prob)
            for i in range(city_num):
                if self.open_table_city[i]:
                    # 轮次相减
                    temp_prob -= select_citys_prob[i]
                    if temp_prob < 0.0:
                        next_city = i
                        break
 
        # 未从概率产生，顺序选择一个未访问城市
        # if next_city == -1:
        #     for i in range(city_num):
        #         if self.open_table_city[i]:
        #             next_city = i
        #             break
 
        if (next_city == -1):
            next_city = random.randint(0, city_num - 1)
            while ((self.open_table_city[next_city]) == False):  # if==False,说明已经遍历过了
                next_city = random.randint(0, city_num - 1)
 
        # 返回下一个城市序号
        return next_city
    
    # 计算路径总距离
    def __cal_total_distance(self):
        
        temp_distance = 0.0
 
        for i in range(1, city_num):
            start, end = self.path[i], self.path[i-1]
            temp_distance += distance_graph[start][end]
 
        # 回路
        end = self.path[0]
        temp_distance += distance_graph[start][end]
        self.total_distance = temp_distance
        
    
    # 移动操作
    def __move(self, next_city):
        
        self.path.append(next_city)
        self.open_table_city[next_city] = False
        self.total_distance += distance_graph[self.current_city][next_city]
        self.current_city = next_city
        self.move_count += 1
        
    # 搜索路径
    def search_path(self):
 
        # 初始化数据
        self.__clean_data()
 
        # 搜素路径，遍历完所有城市为止
        while self.move_count < city_num:
            # 移动到下一个城市
            next_city =  self.__choice_next_city()
            self.__move(next_city)
 
        # 计算路径总长度
        self.__cal_total_distance()
 
#----------- TSP问题 -----------
        
class TSP(object):
 
    def __init__(self, root, width = 800, height = 600, n = city_num):
 
        # 创建画布
        self.root = root                               
        self.width = width      
        self.height = height
        # 城市数目初始化为city_num
        self.n = n
        # tkinter.Canvas
        self.canvas = tkinter.Canvas(
                root,
                width = self.width,
                height = self.height,
                bg = "#EBEBEB",             # 背景白色 
                xscrollincrement = 1,
                yscrollincrement = 1
            )
        self.canvas.pack(expand = tkinter.YES, fill = tkinter.BOTH)
        self.title("TSP蚁群算法(n:初始化 e:开始搜索 s:停止搜索 q:退出程序)")
        self.__r = 5
        self.__lock = threading.RLock()     # 线程锁
 
        self.__bindEvents()
        self.new()
 
        # 计算城市之间的距离
        for i in range(city_num):
            for j in range(city_num):
                temp_distance = pow((distance_x[i] - distance_x[j]), 2) + pow((distance_y[i] - distance_y[j]), 2)
                temp_distance = pow(temp_distance, 0.5)
                distance_graph[i][j] =float(int(temp_distance + 0.5))
 
    # 按键响应程序
    def __bindEvents(self):
 
        self.root.bind("q", self.quite)        # 退出程序
        self.root.bind("n", self.new)          # 初始化
        self.root.bind("e", self.search_path)  # 开始搜索
        self.root.bind("s", self.stop)         # 停止搜索
 
    # 更改标题
    def title(self, s):
 
        self.root.title(s)
 
    # 初始化
    def new(self, evt = None):
 
        # 停止线程
        self.__lock.acquire()
        self.__running = False
        self.__lock.release()
 
        self.clear()     # 清除信息 
        self.nodes = []  # 节点坐标
        self.nodes2 = [] # 节点对象
 
        # 初始化城市节点
        for i in range(len(distance_x)):
            # 在画布上随机初始坐标
            x = distance_x[i]
            y = distance_y[i]
            self.nodes.append((x, y))
            # 生成节点椭圆，半径为self.__r
            node = self.canvas.create_oval(x - self.__r,
                    y - self.__r, x + self.__r, y + self.__r,
                    fill = "#ff0000",      # 填充红色
                    outline = "#000000",   # 轮廓白色
                    tags = "node",
                )
            self.nodes2.append(node)
            # 显示坐标
            self.canvas.create_text(x,y-10,              # 使用create_text方法在坐标（302，77）处绘制文字
                    text = '('+str(x)+','+str(y)+')',    # 所绘制文字的内容
                    fill = 'black'                       # 所绘制文字的颜色为灰色
                )
            
        # 顺序连接城市
        #self.line(range(city_num))
        
        # 初始城市之间的距离和信息素
        for i in range(city_num):
            for j in range(city_num):
                pheromone_graph[i][j] = 1.0
                
        self.ants = [Ant(ID) for ID in range(ant_num)]  # 初始蚁群
        self.best_ant = Ant(-1)                          # 初始最优解
        self.best_ant.total_distance = 1 << 31           # 初始最大距离
        self.iter = 1                                    # 初始化迭代次数 
            
    # 将节点按order顺序连线
    def line(self, order):
        # 删除原线
        self.canvas.delete("line")
        def line2(i1, i2):
            p1, p2 = self.nodes[i1], self.nodes[i2]
            self.canvas.create_line(p1, p2, fill = "#000000", tags = "line")
            return i2
        
        # order[-1]为初始值
        reduce(line2, order, order[-1])
 
    # 清除画布
    def clear(self):
        for item in self.canvas.find_all():
            self.canvas.delete(item)
 
    # 退出程序
    def quite(self, evt):
        self.__lock.acquire()
        self.__running = False
        self.__lock.release()
        self.root.destroy()
        print (u"\n程序已退出...")
        sys.exit()
 
    # 停止搜索
    def stop(self, evt):
        self.__lock.acquire()
        self.__running = False
        self.__lock.release()
        
    # 开始搜索
    def search_path(self, evt = None):
 
        # 开启线程
        self.__lock.acquire()
        self.__running = True
        self.__lock.release()
        
        while self.__running:
            # 遍历每一只蚂蚁
            for ant in self.ants:
                # 搜索一条路径
                ant.search_path()
                # 与当前最优蚂蚁比较
                if ant.total_distance < self.best_ant.total_distance:
                    # 更新最优解
                    self.best_ant = copy.deepcopy(ant)
            # 更新信息素
            self.__update_pheromone_gragh()
            print (u"迭代次数：",self.iter,u"最佳路径总距离：",int(self.best_ant.total_distance))
            # 连线
            self.line(self.best_ant.path)
            # 设置标题
            self.title("TSP蚁群算法(n:随机初始 e:开始搜索 s:停止搜索 q:退出程序) 迭代次数: %d" % self.iter)
            # 更新画布
            self.canvas.update()
            self.iter += 1
 
    # 更新信息素
    def __update_pheromone_gragh(self):
 
        # 获取每只蚂蚁在其路径上留下的信息素
        temp_pheromone = [[0.0 for col in range(city_num)] for raw in range(city_num)]
        for ant in self.ants:
            for i in range(1,city_num):
                start, end = ant.path[i-1], ant.path[i]
                # 在路径上的每两个相邻城市间留下信息素，与路径总距离反比
                temp_pheromone[start][end] += Q / ant.total_distance
                temp_pheromone[end][start] = temp_pheromone[start][end]
 
        # 更新所有城市之间的信息素，旧信息素衰减加上新迭代信息素
        for i in range(city_num):
            for j in range(city_num):
                pheromone_graph[i][j] = pheromone_graph[i][j] * RHO + temp_pheromone[i][j]
 
    # 主循环
    def mainloop(self):
        self.root.mainloop()
 
#----------- 程序的入口处 -----------
                
if __name__ == '__main__':
 
    TSP(tkinter.Tk()).mainloop()

Reference:
https://zh.wikipedia.org/wiki/蚁群算法
https://blog.csdn.net/fanxin_i/article/details/80380733
https://blog.csdn.net/qq_35109096/article/details/81126925st=>start: Start op1=>operation: 初始化 op15=>operation: 随机放置蚂蚁 op2=>operation: 对每只蚂蚁选择下个城市 op3=>operation: 更新信息素 op4=>operation: 输出最好路径 cond1=>condition: 还有城市可选？ cond2=>condition: 达到最大迭代次数？ ed=>end: End st->op1->op15->op2->cond1(no)->op3->cond2(yes)->ed cond1(yes)->op2 cond2(no)->op15{"scale":1,"line-width":2,"line-length":50,"text-margin":10,"font-size":12}