【作者】 刘彦斌；

【导师】 周春光；

【作者基本信息】 吉林大学 ， 计算机应用技术， 2010， 博士

【摘要】 本文在深入研究群智能计算模型和算法的基础上,提出了一种基于agent的自治计算模型,给出模型的基本组成部分和具体实例化过程。并在此基础上应用该模型解决了函数优化问题、无线传感器网络路由问题和集装箱装载问题。其次,根据RDF数据库整合问题特点和对系统、算法的需求,设计并开发一套模糊匹配算法包,集成到应用系统。本文的主要工作内容如下:1)提出一种基于agent的群智能计算模型。模型由系统环境,agent和规则组成,并引入信念的概念到模型中。该研究内容属新颖的基于自治计算领域,同时为群智能模型算法,尤其是多agent的研究带来新思路。2)应用模型解决函数优化问题。该研究内容从多agent系统的本质出发,利用自治、智能、交互等特性,引入信念及信念调整机制,利用其优点解决问题,该工作不仅为多agent的应用开辟新方向,同时也为组合优化问题的研究找到新的切入点。3)应用模型解决无线传感器网络路由问题。该应用能适应传感器网络动态性的特点,为不同规模的网络探查较优路由,减少能量消耗,延长节点寿命,同时保证较低的算法时间复杂性。4)应用模型解决集装箱装载问题。该问题是本文涉及运输系统中的重要模块,系统充分发挥数学理论、计算机技术优势,为推动行业解决方案制定科学化进程起到促进作用。传统数学方法解决此问题有运算时间长的局限性。本节部分工作开拓其它方式解决问题,在保证精度同时减少计算时间。该方法时间优势明显,精度较一般启发式方法有一定优势。5)模糊匹配算法研究。以解决RDF数据库资源匹配及融合为导向,以实用为目标,设计并开发一个集成算法包,该算法包包含文本相似性、语义相似性和词关系计算算法,并集成到应用系统中。更多还原

【Abstract】 The Swarm Intelligence (SI) is the activity created by many individuals in the interacting procedure that shows the satisfactory performance in lots of optimalizing areas, therefore, gaining the attention of scholars in the related fields. SI is a kind of artificial intelligence based on autonomy and non-central control system, it reflects the collaborative power of entity within swarm. The advantage is to find the solution of complex system without the central control and global model, there are many classical applications, such as, ant colony algorithm, multi-agent, PSO (Particle Swarm Optimization) and group robot.The autonomy oriented computing is a new bottom-up paradigm for the practical problem-solving and complex system modeling, especially in the complex system modeling. Constructing the autonomy computing model based on agent is the new idea and new application in SI. After the 20-years research, the agent theory and technology have made great progress and been applied to many areas, multi-agent has a significant inherent advantages in solving distributed problems, the model proposed by this paper will be applied in optimization problem, which is also the research point in this paper.With the development of Web, different datasets managed by different entities may offer similar contents, the fundament of the Semantic Web is the use of URIs (Uniform Resource Identifiers) to identify objects. The use of URIs assures that real world objects can be identified and referred to unambiguously. These features need the automatical RDF resource interlinking tool, which attracts more and more researchers. One of the works in this paper is the foundation research of this area, it mainly includes some classical problems and algorithms in the NLP, and furthermore, we will apply these algorithms into the RDF databases integration system for the practical problem solving.This paper summarizes the SI model and algorithm at first, and presents an agent-based autonomy computing model. We introduce the basic components and instantiation process, and then apply this model to function optimization problem, wireless sensor network routing problem and container stowage problem. Next, based on the feature and demand of RDF dataset integrating system, we design and implement a fuzzy matching algorithm package in the system tool. The contributions of this paper are as follows:(1) Present an agent oriented autonomy computing model. This model is composed of environment, agent and rule, plus belief concept. The system is the environment, is the location of individual activities and interactions, and the platform of rules playing a role and producing results. We will instance the system property according to the different application issues. The rule is the policy of individual existence and activities, it leads to the overwhelming ability of swarm, it’s also the system rule. As the standard of the individual existing, the model presented by this paper is a kind of the SI, and contains the rules of selecting, interacting, adjusting and evaluating. The agent model needs the definitions of the individual behavior and property, one agent is an independent entity, is the core of model, and the model of agent is problem-related. This research work belongs to the novel autonomy oriented computing field, and brings in the new approach for the SI model research, especially multi-agent.(2) Solve the function optimization problem using this model. We choose the domain of definition of the function as the existence environment of the agent, and choose the return value as the target of the agent. Each agent is given a belief randomly in the beginning, in the period of each iteration of the system, all individuals decide the directions of moving on and the size of step according to its own belief by using the learning machine, then adjust the belief according to the changes of the return value after moving. The adjustment of belief makes agent can have an evaluation of its path, so agent can vary its belief at any time to make it tend the target soon. The detailed strategy is that after walking over one step, agent compares the function values of different times according to the target function, if what this step walks is closer to the best solution, strengthen the intensity of the belief. Otherwise, weaken it. If belief is small enough to arrive at a certain value, a new random direction and intensity will be given to make it continue to iterate. Adjusting belief intensity makes the searching of agent is similar to the process of local climbing, which can tend best solution quickly, and avoid the agent to sink into local peak because of the variety of the intensity, either. At last, agent interacts with others in the same scope. This application not only opens up the new direction for agent area, but also finds a new method for the research of the combinatorial optimization problem. The previous study of the agent system is generally from the perspective of genetic algorithm combining with the agent, this paper uses autonomy, intelligent, interaction and other features, brings in belief and corresponding adjustment strategy, utilizes the advantage in the problem solving. The experiment uses the single peak function, continuous multi-peak function and multi-peak function with many local minima testing algorithm, and accepts the average value of repeated runs avoiding the unscientific nature of random solution, the results show that it fast finds the global optimum under the constraints of the iteration number and initial swarm population, which verifies the validity.(3) Solve wireless sensor networks routing problem. Agents exist in the environment, each agent stands for a total routing. In this paper, agent’s purpose is defined as the minimum of energy dissipation of its routing. Agent will decide its own action according to its belief matrix in the process of iteration to attain the purpose of tending target. Belief is an abstract concept of intelligence, which will affect movement of agents. Each agent has a two-dimensional belief matrix, which is created according to sensor connection status in environment, and matrix[i][j] value is set by a random method based on energy dissipation of communication between sensor node i and sensor j. This application can adapt to the dynamic of the sensor networks, and obtain the better routing for the network, reduce the power dismission, prolong the sensor node’s lifespan with the relatively low time complexity. In the experiment, we use the different scale networks, the environment of wireless sensor networks is a 200m*200m square, the number of sensor nodes as 100, 200, 300, 400, and 500. Let the transmitted data size of one sensor be 1k bit, launch radiuses are 20m and 30m. The results show that this approach can detect the valid data collecting path for the sink node in the WSNs. Compared with others, the results in this paper are better in small-scale and medium-scale networks, and a slightly different in large-scale networks. Another evaluation of routing algorithm is the lifetime of wireless sensor networks, which can be calculated by energy dissipation indirectly, the result shows that the network life of this paper has a greater improvement under most circumstances.(4) Solve the container stowage problem. This problem is derived from an applied research project in this paper, it is the core component in this system. We first model this problem and set the available space of the vessel as the environment, it’s a three-dimensional structure. The agent’s property depends on its position. Belief is an abstract concept of intelligence, which will affect agent in two ways: one is that belief direction affects agent search direction; the other is that belief strength value affects search step, the greater the value, the longer the step. Belief adjustment is the result of agent evaluates search path. It makes agent achieve objective more quickly and exactly. There are some computing time limitations to use the traditional mathematical methods, this section aims to solve problem by other approaches in ensuring accuracy while reducing computing time. For verifying the validity of AOACM in solving this problem, the experiment uses the 900TEU and 1200TEU vessels. In the comparison with the random method, the AOACM’s result of the 130-200 iterations is better than the 1.5 millon random result in some issues, although 1.5 million is very small in the whole search space, the results are meaningful as the random method. In the comparison with another outstanding algorithm:SH, it shows that the approach presented in this paper has the obvious time advantage, and the better precision than the heuristic algorithms.(5) Research on the fuzzy matching algorithm. This kind of algorithm contains the string similarity algorithm, the semantical similarity approach and the word relation algorithm. This paper presents an integrated algorithm package in the direction of the RDF database resource matching, fusing problem, and the object of the application. This package includes sequence alignment and Lee ML’s RS fuzzy matching algorithm of text similarity, the semantical similarity based on WordNet, its core is to count the relationship of all the words in a sequence with synonym set of words in another sequence, and the word relation algorithm based on SKOS, the method is computing the distance of the words in the classification, these three approaches will be integrated in the system. We employ two kinds of the dataset to verify the system and algorithm, one is domain independent database, and the other is domain-related, the results show the well performance, the better precision, recall and F-Measure. Now, the computer scientist pay more and more attention to the research of the SI computing algorithm, especially the autonomy computing model, the research works of the thesis will greatly enrich the studies of this area. The research and the technology method are novel in both theoretical and technological aspects, which will push the development in circumstance of the domestic nascent research.更多还原