A Hybrid Immunological Search for the Weighted Feedback Vertex Set Problem View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2020-01-22

AUTHORS

Vincenco Cutello , Maria Oliva , Mario Pavone , Rocco A. Scollo

ABSTRACT

In this paper we present a hybrid immunological inspired algorithm (Hybrid-IA) for solving the Minimum Weighted Feedback Vertex Set (MWFVS) problem. MWFVS is one of the most interesting and challenging combinatorial optimization problem, which finds application in many fields and in many real life tasks. The proposed algorithm is inspired by the clonal selection principle, and therefore it takes advantage of the main strength characteristics of the operators of (i) cloning; (ii) hypermutation; and (iii) aging. Along with these operators, the algorithm uses a local search procedure, based on a deterministic approach, whose purpose is to refine the solutions found so far. In order to evaluate the efficiency and robustness of Hybrid-IA several experiments were performed on different instances, and for each instance it was compared to three different algorithms: (1) a memetic algorithm based on a genetic algorithm (MA); (2) a tabu search metaheuristic (XTS); and (3) an iterative tabu search (ITS). The obtained results prove the efficiency and reliability of hybrid-IA on all instances in term of the best solutions found and also similar performances with all compared algorithms, which represent nowadays the state-of-the-art on for MWFVS problem. More... »

PAGES

1-16

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-030-38629-0_1

DOI

http://dx.doi.org/10.1007/978-3-030-38629-0_1

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1124216802


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0801", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Artificial Intelligence and Image Processing", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Mathematics and Computer Science, University of Catania, V.le A. Doria 6, 95125, Catania, Italy", 
          "id": "http://www.grid.ac/institutes/grid.8158.4", 
          "name": [
            "Department of Mathematics and Computer Science, University of Catania, V.le A. Doria 6, 95125, Catania, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Cutello", 
        "givenName": "Vincenco", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Mathematics and Computer Science, University of Catania, V.le A. Doria 6, 95125, Catania, Italy", 
          "id": "http://www.grid.ac/institutes/grid.8158.4", 
          "name": [
            "Department of Mathematics and Computer Science, University of Catania, V.le A. Doria 6, 95125, Catania, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Oliva", 
        "givenName": "Maria", 
        "id": "sg:person.012340437717.50", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012340437717.50"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Mathematics and Computer Science, University of Catania, V.le A. Doria 6, 95125, Catania, Italy", 
          "id": "http://www.grid.ac/institutes/grid.8158.4", 
          "name": [
            "Department of Mathematics and Computer Science, University of Catania, V.le A. Doria 6, 95125, Catania, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Pavone", 
        "givenName": "Mario", 
        "id": "sg:person.07350620665.82", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07350620665.82"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Mathematics and Computer Science, University of Catania, V.le A. Doria 6, 95125, Catania, Italy", 
          "id": "http://www.grid.ac/institutes/grid.8158.4", 
          "name": [
            "Department of Mathematics and Computer Science, University of Catania, V.le A. Doria 6, 95125, Catania, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Scollo", 
        "givenName": "Rocco A.", 
        "id": "sg:person.016661443761.18", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016661443761.18"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2020-01-22", 
    "datePublishedReg": "2020-01-22", 
    "description": "In this paper we present a hybrid immunological inspired algorithm (Hybrid-IA) for solving the Minimum Weighted Feedback Vertex Set (MWFVS) problem. MWFVS is one of the most interesting and challenging combinatorial optimization problem, which finds application in many fields and in many real life tasks. The proposed algorithm is inspired by the clonal selection principle, and therefore it takes advantage of the main strength characteristics of the operators of (i) cloning; (ii) hypermutation; and (iii) aging. Along with these operators, the algorithm uses a local search procedure, based on a deterministic approach, whose purpose is to refine the solutions found so far. In order to evaluate the efficiency and robustness of Hybrid-IA several experiments were performed on different instances, and for each instance it was compared to three different algorithms: (1) a memetic algorithm based on a genetic algorithm (MA); (2) a tabu search metaheuristic (XTS); and (3) an iterative tabu search (ITS). The obtained results prove the efficiency and reliability of hybrid-IA on all instances in term of the best solutions found and also similar performances with all compared algorithms, which represent nowadays the state-of-the-art on for MWFVS problem.", 
    "editor": [
      {
        "familyName": "Matsatsinis", 
        "givenName": "Nikolaos F.", 
        "type": "Person"
      }, 
      {
        "familyName": "Marinakis", 
        "givenName": "Yannis", 
        "type": "Person"
      }, 
      {
        "familyName": "Pardalos", 
        "givenName": "Panos", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-030-38629-0_1", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-030-38628-3", 
        "978-3-030-38629-0"
      ], 
      "name": "Learning and Intelligent Optimization", 
      "type": "Book"
    }, 
    "keywords": [
      "challenging combinatorial optimization problems", 
      "Weighted Feedback Vertex Set Problem", 
      "tabu search metaheuristic", 
      "combinatorial optimization problems", 
      "local search procedure", 
      "clonal selection principle", 
      "real-life tasks", 
      "Feedback Vertex Set problem", 
      "search metaheuristic", 
      "tabu search", 
      "memetic algorithm", 
      "different algorithms", 
      "set problem", 
      "search procedure", 
      "different instances", 
      "genetic algorithm", 
      "best solution", 
      "algorithm", 
      "optimization problem", 
      "feedback vertex", 
      "hybrid IA", 
      "similar performance", 
      "immunological searches", 
      "instances", 
      "life tasks", 
      "selection principle", 
      "deterministic approach", 
      "metaheuristics", 
      "main strength characteristics", 
      "search", 
      "operators", 
      "task", 
      "robustness", 
      "efficiency", 
      "solution", 
      "art", 
      "applications", 
      "performance", 
      "reliability", 
      "vertices", 
      "advantages", 
      "order", 
      "experiments", 
      "principles", 
      "terms", 
      "field", 
      "purpose", 
      "state", 
      "results", 
      "characteristics", 
      "procedure", 
      "problem", 
      "approach", 
      "hypermutation", 
      "strength characteristics", 
      "aging", 
      "cloning", 
      "paper"
    ], 
    "name": "A Hybrid Immunological Search for the Weighted Feedback Vertex Set Problem", 
    "pagination": "1-16", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1124216802"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-030-38629-0_1"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-030-38629-0_1", 
      "https://app.dimensions.ai/details/publication/pub.1124216802"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-20T07:47", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220519/entities/gbq_results/chapter/chapter_375.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-030-38629-0_1"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-030-38629-0_1'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-030-38629-0_1'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-030-38629-0_1'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-030-38629-0_1'


 

This table displays all metadata directly associated to this object as RDF triples.

148 TRIPLES      23 PREDICATES      83 URIs      76 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-030-38629-0_1 schema:about anzsrc-for:08
2 anzsrc-for:0801
3 schema:author Ne380a8f6a66b4ce290788d809a251221
4 schema:datePublished 2020-01-22
5 schema:datePublishedReg 2020-01-22
6 schema:description In this paper we present a hybrid immunological inspired algorithm (Hybrid-IA) for solving the Minimum Weighted Feedback Vertex Set (MWFVS) problem. MWFVS is one of the most interesting and challenging combinatorial optimization problem, which finds application in many fields and in many real life tasks. The proposed algorithm is inspired by the clonal selection principle, and therefore it takes advantage of the main strength characteristics of the operators of (i) cloning; (ii) hypermutation; and (iii) aging. Along with these operators, the algorithm uses a local search procedure, based on a deterministic approach, whose purpose is to refine the solutions found so far. In order to evaluate the efficiency and robustness of Hybrid-IA several experiments were performed on different instances, and for each instance it was compared to three different algorithms: (1) a memetic algorithm based on a genetic algorithm (MA); (2) a tabu search metaheuristic (XTS); and (3) an iterative tabu search (ITS). The obtained results prove the efficiency and reliability of hybrid-IA on all instances in term of the best solutions found and also similar performances with all compared algorithms, which represent nowadays the state-of-the-art on for MWFVS problem.
7 schema:editor N2d51c2ff9269451c93e87f2f209727c4
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N3b971bb4a79e42cdb1e0f3bc78da6c44
12 schema:keywords Feedback Vertex Set problem
13 Weighted Feedback Vertex Set Problem
14 advantages
15 aging
16 algorithm
17 applications
18 approach
19 art
20 best solution
21 challenging combinatorial optimization problems
22 characteristics
23 clonal selection principle
24 cloning
25 combinatorial optimization problems
26 deterministic approach
27 different algorithms
28 different instances
29 efficiency
30 experiments
31 feedback vertex
32 field
33 genetic algorithm
34 hybrid IA
35 hypermutation
36 immunological searches
37 instances
38 life tasks
39 local search procedure
40 main strength characteristics
41 memetic algorithm
42 metaheuristics
43 operators
44 optimization problem
45 order
46 paper
47 performance
48 principles
49 problem
50 procedure
51 purpose
52 real-life tasks
53 reliability
54 results
55 robustness
56 search
57 search metaheuristic
58 search procedure
59 selection principle
60 set problem
61 similar performance
62 solution
63 state
64 strength characteristics
65 tabu search
66 tabu search metaheuristic
67 task
68 terms
69 vertices
70 schema:name A Hybrid Immunological Search for the Weighted Feedback Vertex Set Problem
71 schema:pagination 1-16
72 schema:productId N1189b64cf5754e99a7f383b8ececec66
73 Nbceb26ef87a24b1c8d70900f57e6b44c
74 schema:publisher Nb2de9317de224a3497fb4c99c60fe39b
75 schema:sameAs https://app.dimensions.ai/details/publication/pub.1124216802
76 https://doi.org/10.1007/978-3-030-38629-0_1
77 schema:sdDatePublished 2022-05-20T07:47
78 schema:sdLicense https://scigraph.springernature.com/explorer/license/
79 schema:sdPublisher N97b6db6a5b7b4918893127e7e95a16f4
80 schema:url https://doi.org/10.1007/978-3-030-38629-0_1
81 sgo:license sg:explorer/license/
82 sgo:sdDataset chapters
83 rdf:type schema:Chapter
84 N04a5795e9ea44ff1b9557edb0dfc4faa rdf:first N68fd1b5293ba4a4b9f47859b8564a29b
85 rdf:rest rdf:nil
86 N1189b64cf5754e99a7f383b8ececec66 schema:name doi
87 schema:value 10.1007/978-3-030-38629-0_1
88 rdf:type schema:PropertyValue
89 N201d4a5d350f424a908b923c04a18e39 rdf:first sg:person.012340437717.50
90 rdf:rest Nd9d0626e8c7543709ab98564d49bebfc
91 N2c69bcfb87fb41af9acfc4f0d85e8d52 schema:familyName Marinakis
92 schema:givenName Yannis
93 rdf:type schema:Person
94 N2d51c2ff9269451c93e87f2f209727c4 rdf:first N47e97910c88b4c0b955fc9adcb2cf83d
95 rdf:rest N5d86f811d54849c19b65a85566119f7e
96 N3b971bb4a79e42cdb1e0f3bc78da6c44 schema:isbn 978-3-030-38628-3
97 978-3-030-38629-0
98 schema:name Learning and Intelligent Optimization
99 rdf:type schema:Book
100 N47e97910c88b4c0b955fc9adcb2cf83d schema:familyName Matsatsinis
101 schema:givenName Nikolaos F.
102 rdf:type schema:Person
103 N5d86f811d54849c19b65a85566119f7e rdf:first N2c69bcfb87fb41af9acfc4f0d85e8d52
104 rdf:rest N04a5795e9ea44ff1b9557edb0dfc4faa
105 N68fd1b5293ba4a4b9f47859b8564a29b schema:familyName Pardalos
106 schema:givenName Panos
107 rdf:type schema:Person
108 N6f8e823ed9ba4d62a2b84ec288a52d34 schema:affiliation grid-institutes:grid.8158.4
109 schema:familyName Cutello
110 schema:givenName Vincenco
111 rdf:type schema:Person
112 N97b6db6a5b7b4918893127e7e95a16f4 schema:name Springer Nature - SN SciGraph project
113 rdf:type schema:Organization
114 Nb2de9317de224a3497fb4c99c60fe39b schema:name Springer Nature
115 rdf:type schema:Organisation
116 Nbceb26ef87a24b1c8d70900f57e6b44c schema:name dimensions_id
117 schema:value pub.1124216802
118 rdf:type schema:PropertyValue
119 Nd35d037fe7bb4d6d82ab71b5b9920c16 rdf:first sg:person.016661443761.18
120 rdf:rest rdf:nil
121 Nd9d0626e8c7543709ab98564d49bebfc rdf:first sg:person.07350620665.82
122 rdf:rest Nd35d037fe7bb4d6d82ab71b5b9920c16
123 Ne380a8f6a66b4ce290788d809a251221 rdf:first N6f8e823ed9ba4d62a2b84ec288a52d34
124 rdf:rest N201d4a5d350f424a908b923c04a18e39
125 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
126 schema:name Information and Computing Sciences
127 rdf:type schema:DefinedTerm
128 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
129 schema:name Artificial Intelligence and Image Processing
130 rdf:type schema:DefinedTerm
131 sg:person.012340437717.50 schema:affiliation grid-institutes:grid.8158.4
132 schema:familyName Oliva
133 schema:givenName Maria
134 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012340437717.50
135 rdf:type schema:Person
136 sg:person.016661443761.18 schema:affiliation grid-institutes:grid.8158.4
137 schema:familyName Scollo
138 schema:givenName Rocco A.
139 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016661443761.18
140 rdf:type schema:Person
141 sg:person.07350620665.82 schema:affiliation grid-institutes:grid.8158.4
142 schema:familyName Pavone
143 schema:givenName Mario
144 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07350620665.82
145 rdf:type schema:Person
146 grid-institutes:grid.8158.4 schema:alternateName Department of Mathematics and Computer Science, University of Catania, V.le A. Doria 6, 95125, Catania, Italy
147 schema:name Department of Mathematics and Computer Science, University of Catania, V.le A. Doria 6, 95125, Catania, Italy
148 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...