Lamarckian memetic algorithms: local optimum and connectivity structure analysis

Memetic algorithms (MAs) represent an emerging field that has attracted increasing research interest in recent times. Despite the popularity of the field, we remain to know rather little of the search mechanisms of MAs. Given the limited progress made on revealing the intrinsic properties of some commonly used complex benchmark problems and working mechanisms of Lamarckian memetic algorithms in general non-linear programming, we introduce in this work for the first time the concepts of local optimum structure and generalize the notion of neighborhood to connectivity structure for analysis of MAs. Based on the two proposed concepts, we analyze the solution quality and computational efficiency of the core search operators in Lamarckian memetic algorithms. Subsequently, the structure of local optimums of a few representative and complex benchmark problems is studied to reveal the effects of individual learning on fitness landscape and to gain clues into the success or failure of MAs. The connectivity structure of local optimum for different memes or individual learning procedures in Lamarckian MAs on the benchmark problems is also investigated to understand the effects of choice of memes in MA design.     

Extra edge connectivity and isoperimetric edge connectivity

An edge set S of a connected graph G is a k-extra edge cut, if G-S is no longer connected, and each component of G-S has at least k vertices. The cardinality of a minimum k-extra edge cut, denoted by λ_k(G), is the k-extra edge connectivity of G. The kth isoperimetric edge connectivity γ_k(G) is defined as , where ω(U) is the number of edges with one end in U and the other end in . Write β_k(G)=min{ω(U):U⊂V(G),|U|=k}. A graph G with is said to be γ_k-optimal.In this paper, we first prove that λ_k(G)=γ_k(G) if G is a regular graph with girth g?k/2. Then, we show that except for K_3,3 and K₄, a 3-regular vertex/edge transitive graph is γ_k-optimal if and only if its girth is at least k+2. Finally, we prove that a connected d-regular edge-transitive graph with d?6e_k(G)/k is γ_k-optimal, where e_k(G) is the maximum number of edges in a subgraph of G with order k.     

Mapping the global structure of TSP fitness landscapes

The global structure of combinatorial landscapes is not fully understood, yet it is known to impact the performance of heuristic search methods. We use a so-called local optima network model to characterise and visualise the global structure of travelling salesperson fitness landscapes of different classes, including random and structured real-world instances of realistic size. Our study brings rigour to the characterisation of so-called funnels, and proposes an intensive and effective sampling procedure for extracting the networks. We propose enhanced visualisation techniques, including 3D plots and the incorporation of colour, sizes and widths, to reflect relevant aspects of the search process. This brings an almost tangible new perspective to the landscape and funnel metaphors. Our results reveal a much richer global structure than the suggestion of a ‘big-valley’ structure. Most landscapes of the tested instances have multiple valleys or funnels; and the number, disposition and interaction of these funnels seem to relate to search difficulty on the studied landscapes. We also find that the structured TSP instances feature high levels of neutrality, an observation not previously reported in the literature. We then propose ways of analysing and visualising these neutral landscapes.     

Graphs with prescribed connectivity and line graph connectivity

Chartrand and Stewart have shown that the line graph of an n-connected graph is itself n-connected. This paper shows that for every pair of integers m > n > 1 there is a graph of point connectivity n whose line graph has point connectivity m. The corresponding question for line connectivity is also resolved.     

Degree sequences and edge connectivity

For each positive integer k, we give a finite list C(k) of Bondy–Chvátal type conditions on a nondecreasing sequence \(d=(d_1,\dots ,d_n)\) of nonnegative integers such that every graph on n vertices with degree sequence at least d is k-edge-connected. These conditions are best possible in the sense that whenever one of them fails for d then there is a graph on n vertices with degree sequence at least d which is not k-edge-connected. We prove that C(k) is and must be large by showing that it contains p(k) many logically irredundant conditions, where p(k) is the number of partitions of k. Since, in the corresponding classic result on vertex connectivity, one needs just one such condition, this is one of the rare statements where the edge connectivity version is much more difficult than the vertex connectivity version. Furthermore, we demonstrate how to handle other types of edge-connectivity, such as, for example, essential k-edge-connectivity. We prove that any sublist equivalent to C(k) has length at least p(k), where p(k) is the number of partitions of k, which is in contrast to the corresponding classic result on vertex connectivity where one needs just one such condition. Furthermore, we demonstrate how to handle other types of edge-connectivity, such as, for example, essential k-edge-connectivity. Finally, we informally describe a simple and fast procedure which generates the list C(k). Specialized to \(k=3\), this verifies a conjecture of Bauer, Hakimi, Kahl, and Schmeichel, and for \(k=2\) we obtain an alternative proof for their result on bridgeless connected graphs. The explicit list for \(k=4\) is given, too.     

Hypergraph connectivity augmentation

Received May 1995 / Revised version received May 1996 Published online March 16, 1999     

Colorful monochromatic connectivity

An edge-coloring of a connected graph is monochromatically-connecting if there is a monochromatic path joining any two vertices. How “colorful” can a monochromatically-connecting coloring be? Let mc(G) denote the maximum number of colors used in a monochromatically-connecting coloring of a graph G. We prove some nontrivial upper and lower bounds for mc(G) and relate it to other graph parameters such as the chromatic number, the connectivity, the maximum degree, and the diameter.     

Short cycle connectivity

Short cycle connectivity is a generalization of ordinary connectivity—two vertices have to be connected by a sequence of short cycles, in which two consecutive cycles have at least one common vertex. If all consecutive cycles in the sequence share at least one edge, we talk about edge short cycle connectivity. Short cycle connectivity can be extended to directed graphs (cyclic and transitive connectivity).It is shown that the short cycle connectivity is an equivalence relation on the set of vertices, while the edge/arc short cycle connectivity components determine an equivalence relation on the set of edges/arcs.     

On matroid connectivity

Three types of matroid connectivity, including Tutte's, are defined and shown to generalize corresponding notions of graph connectivity. A theorem of Tutte on cyclically 3-connected graphs, is generalized to matroids.     

On edge connectivity and parity factor

By Petersen's Theorem, a bridgeless cubic graph has a 2-factor. Fleischner(Discrete Math.,101, 33–37(1992)) has extended this result to bridgeless graphs of minimum degree at least three by showing that every such graph has an even factor without isolated vertices. Let me 0 be even and mo 0 be odd. In this paper, we prove that every m e-edge-connected graph with minimum degree at least me + 1 contains an even factor with minimum degree at least m e and every(m o + 1)-edge-connected graph contains an odd factor with minimum degree at least m o, which further extends Fleischner's result. Moreover, we show that our results are best possible.     

Algebraic cycles and Hodge theoretic connectivity

Oblatum 19-VI-1991 & 4-III-1992     

Upper embeddability and connectivity of graphs

In this paper, we prove that every cyclically 4-edge-connected graph is upper-embeddable. The proof is based on the study of the effect on the maximum genus of a graph when one of its subgraphs is collapsed to a vertex.     

On prime ends and local connectivity

Let U be a simply connected domain whose complement K = \ U contains more than one point. We show that the impressionof a prime end of U contains at most two points at which K islocally connected. This is achieved by establishing a characterizationof local connectivity of K at a point z₀ U in terms of theprime ends of U whose impressions contain z₀, and then invokinga result of Ursell and Young.     

On shredders and vertex connectivity augmentation

We consider the following problem: given a k-(node) connected graph G find a smallest set F of new edges so that the graph G+F is (k+1)-connected. The complexity status of this problem is an open question. The problem admits a 2-approximation algorithm. Another algorithm due to Jordán computes an augmenting edge set with at most (k−1)/2 edges over the optimum. CV(G) is a k-separator (k-shredder) of G if |C|=k and the number b(C) of connected components of G−C is at least two (at least three). We will show that the problem is polynomially solvable for graphs that have a k-separator C with b(C)k+1. This leads to a new splitting-off theorem for node connectivity. We also prove that in a k-connected graph G on n nodes the number of k-shredders with at least p components (p3) is less than 2n/(2p−3), and that this bound is asymptotically tight.     

Classes of network connectivity and dynamics

Many kinds of complex systems exhibit characteristic patterns of temporal correlations that emerge as the result of functional interactions within a structured network. One such complex system is the brain, composed of numerous neuronal units linked by synaptic connections. The activity of these neuronal units gives rise to dynamic states that are characterized by specific patterns of neuronal activation and co‐activation. These patterns, called functional connectivity, are possible neural correlates of perceptual and cognitive processes. Which functional connectivity patterns arise depends on the anatomical structure of the underlying network, which in turn is modified by a broad range of activity‐dependent processes. Given this intricate relationship between structure and function, the question of how patterns of anatomical connectivity constrain or determine dynamical patterns is of considerable theoretical importance. The present study develops computational tools to analyze networks in terms of their structure and dynamics. We identify different classes of network, including networks that are characterized by high complexity. These highly complex networks have distinct structural characteristics such as clustered connectivity and short wiring length similar to those of large‐scale networks of the cerebral cortex. © 2002 Wiley Periodicals, Inc.     

Pancyclic arcs and connectivity in tournaments

A tournament is an orientation of the edges of a complete graph. An arc is pancyclic in a tournament T if it is contained in a cycle of length l, for every 3 ≤ l ≤ |T|. Let p(T) denote the number of pancyclic arcs in a tournament T. In 4 , Moon showed that for every non‐trivial strong tournament T, p(T) ≥ 3. Actually, he proved a somewhat stronger result: for any non‐trivial strong tournament h(T) ≥ 3 where h(T) is the maximum number of pancyclic arcs contained in the same hamiltonian cycle of T. Moreover, Moon characterized the tournaments with h(T) = 3. All these tournaments are not 2‐strong. In this paper, we investigate relationship between the functions p(T) and h(T) and the connectivity of the tournament T. Let p_k(n) := min {p(T), T k‐strong tournament of order n} and h_k(n) := min{h(T), T k‐strong tournament of order n}. We conjecture that (for k ≥ 2) there exists a constant α_k> 0 such that p_k(n) ≥ α_kn and h_k(n) ≥ 2k+1. In this paper, we establish the later conjecture when k = 2. We then characterized the tournaments with h(T) = 4 and those with p(T) = 4. We also prove that for k ≥ 2, p_k(n) ≥ 2k+3. At last, we characterize the tournaments having exactly five pancyclic arcs. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 87–110, 2004     

Distance connectivity in graphs and digraphs

Let G = (V, A) be a digraph with diameter D ≠ 1. For a given integer 2 ≤ t ≤ D, the t-distance connectivity κ(t) of G is the minimum cardinality of an x → y separating set over all the pairs of vertices x, y which are at distance d(x, y) ≥ t. The t-distance edge connectivity λ(t) of G is defined similarly. The t-degree of G, δ(t), is the minimum among the out-degrees and in-degrees of all vertices with (out- or -in-) eccentricity at least t. A digraph is said to be maximally distance connected if κ(t) = δ(t) for all values of t. In this paper we give a construction of a digraph having D − 1 positive arbitrary integers c₂ ≤ … ≤ c_D, D > 3, as the values of its t-distance connectivities κ(2) = c₂, …, κ(D) = c_D. Besides, a digraph that shows the independence of the parameters κ(t), λ(t), and δ(t) is constructed. Also we derive some results on the distance connectivities of digraphs, as well as sufficient conditions for a digraph to be maximally distance connected. Similar results for (undirected) graphs are presented. © 1996 John Wiley & Sons, Inc.     

Degree and local connectivity in digraphs

It is shown that there is a digraphD of minimum outdegree 12m and μ(x, y; D)=11m, but every digraphD of minimum outdegreen contains verticesx ≠y withλ(x, y; D)≧n−1, whereμ(x, y; D) andλ(x, y; D) denote the maximum number of openly disjoint and edge-disjoint paths, respectively.     

Theorems on matroid connectivity

It is proved that for every k?4 there is a Δ(k) such that for every g there is a graph G with maximal degree at most Δ(k), chromatic number at least k and girth at least g. In fact, for a fixed k, the restriction of the maximal degree to Δ(k) does not seem to slow down the growth of the maximal girth of a k-chromatic graph of order n as n → ∞.