Several micro economic models allow to evaluate consumer's behavior using a utility function that is able to measure the success of an individual's decision. Such a decision may consist of a tuple of goods an ...
详细信息
Several micro economic models allow to evaluate consumer's behavior using a utility function that is able to measure the success of an individual's decision. Such a decision may consist of a tuple of goods an individual would like to buy and hours of work necessary to pay for them. The utility of such a decision depends not only on purchase and consumption of goods, but also on fringe benefits such as leisure, which additionally increases the utility to the individual. Utility can be used then as a collective measure for the overall evaluation of societies. In this paper, we present and compare three different agent based social simulations in which the decision finding process of consumers is performed by three algorithms from swarm intelligence and evolutionary computation. Although all algorithms appear to be suitable for the underlying problem as they are based on historical information and also contain a stochastic part which allows for modeling the uncertainty and bounded rationality, they differ greatly in terms of incorporating historical information used for finding new alternative decisions. Newly created decisions that violate underlying budget constraints may either be mapped back to the feasible region, or may be allowed to leave the valid search space. However, in order to avoid biases that would disrupt the inner rationale of each meta heuristic, such invalid decisions are not remembered in the future. Experiments indicate that the choice of such bounding strategy varies according to the choice of the optimization algorithm. Moreover, it seems that each of the techniques could excel in identifying different types of individual behavior such as risk affine, cautious and balanced.
We propose an improved version of the recently developed Enhanced Fireworks Algorithm (EFWA) based on an adaptive dynamic local search mechanism. In EFWA, the explosion amplitude (i.e., search area around the current ...
详细信息
We propose an improved version of the recently developed Enhanced Fireworks Algorithm (EFWA) based on an adaptive dynamic local search mechanism. In EFWA, the explosion amplitude (i.e., search area around the current location) of each firework is computed based on the quality of the firework's current location. This explosion amplitude is limited by a lower bound which decreases with the number of iterations in order to avoid the explosion amplitude to be [close to] zero, and in order to enhance global search abilities at the beginning and local search abilities towards the later phase of the algorithm. As the explosion amplitude in EFWA depends solely on the fireworks' fitness and the current number of iterations, this procedure does not allow for an adaptive optimization process. To deal with these limitations, we propose the Dynamic Search Fireworks Algorithm (dynFWA) which uses a dynamic explosion amplitude for the firework at the currently best position. If the fitness of the best firework could be improved, the explosion amplitude will increase in order to speed up convergence. On the contrary, if the current position of the best firework could not be improved, the explosion amplitude will decrease in order to narrow the search area. In addition, we show that one of the EFWA operators can be removed in dynFWA without a loss in accuracy - this makes dynFWA computationally more efficient than EFWA. Experiments on 28 benchmark functions indicate that dynFWA is able to significantly outperform EFWA, and achieves better performance than the latest SPSO version SPSO2011.
We study the verification problem in distributed networks, stated as follows. Let H be a subgraph of a network G where each vertex of G knows which edges incident on it are in H. We would like to verify whether H has ...
详细信息
We study the verification problem in distributed networks, stated as follows. Let H be a subgraph of a network G where each vertex of G knows which edges incident on it are in H. We would like to verify whether H has some properties, e.g., if it is a tree or if it is connected (every node knows at the end of the process whether H has the specified property or not). We would like to perform this verification in a decentralized fashion via a distributed algorithm. The time complexity of verification is measured as the number of rounds of distributed communication. In this paper we initiate a systematic study of distributed verification and give almost tight lower bounds on the running time of distributed verification algorithms for many fundamental problems such as connectivity, spanning connected subgraph, and s-t cut verification. We then show applications of these results in deriving strong unconditional time lower bounds on the hardness of distributed approximation for many classical optimization problems including minimum spanning tree (MST), shortest paths, and minimum cut. Many of these results are the first nontrivial lower bounds for both exact and approximate distributed computation, and they resolve previous open questions. Moreover, our unconditional lower bound of approximating MST subsumes and improves upon the previous hardness of approximation bound of Elkin [M. Elkin, SIAM J. Comput., 36 (2006), pp. 433-456] as well as the lower bound for (exact) MST computation of Peleg and Rubinovich [D. Peleg and V. Rubinovich, SIAM J. Comput., 30 (2000), pp. 1427-1442]. Our result implies that there can be no distributed approximation algorithm for MST that is significantly faster than the current exact algorithm for any approximation factor. Our lower bound proofs show an interesting connection between communication complexity and distributed computing which turns out to be useful in establishing the time complexity of exact and approximate distributed computatio
暂无评论