Local optima networks of hard combinatorial landscapes

Combinatorial optimization involves finding an optimal solution in a finite set of options; many everyday life problems are of this kind. However, the number of options grows exponentially with the size of the problem, such that an exhaustive search for the best solution is practically infeasible beyond a certain problem size. When efficient algorithms are not available, a practical approach to obtain an approximate solution to the problem at hand, is to start with an educated guess and gradually refine it until we have a good-enough solution. Roughly speaking, this is how local search heuristics work. These stochastic algorithms navigate the problem search space by iteratively turning the current solution into new candidate solutions, guiding the search towards better solutions. The search performance, therefore, depends on structural aspects of the search space, which in turn depend on the move operator being used to modify solutions. A common way to characterize the search space of a problem is through the study of its fitness landscape, a mathematical object comprising the space of all possible solutions, their value with respect to the optimization objective, and a relationship of neighborhood defined by the move operator. The landscape metaphor is used to explain the search dynamics as a sort of potential function. The concept is indeed similar to that of potential energy surfaces in physical chemistry. Borrowing ideas from that field, we propose to extend to combinatorial landscapes the notion of the inherent network formed by energy minima in energy landscapes. In our case, energy minima are the local optima of the combinatorial problem, and we explore several definitions for the network edges. At first, we perform an exhaustive sampling of local optima basins of attraction, and define weighted transitions between basins by accounting for all the possible ways of crossing the basins frontier via one random move. Then, we reduce the computational burden by only counting the chances of escaping a given basin via random kick moves that start at the local optimum. Finally, we approximate network edges from the search trajectory of simple search heuristics, mining the frequency and inter-arrival time with which the heuristic visits local optima. Through these methodologies, we build a weighted directed graph that provides a synthetic view of the whole landscape, and that we can characterize using the tools of complex networks science. We argue that the network characterization can advance our understanding of the structural and dynamical properties of hard combinatorial landscapes. We apply our approach to prototypical problems such as the Quadratic Assignment Problem, the NK model of rugged landscapes, and the Permutation Flow-shop Scheduling Problem. We show that some network metrics can differentiate problem classes, correlate with problem non-linearity, and predict problem hardness as measured from the performances of trajectory-based local search heuristics.

From rifting to passive margin - The examples of the Red Sea, Central Atlantic and Alpine Tethys

Evolution of the Red Sea/Gulf of Suez and the Central Atlantic rift systems shows that an initial, transtensive rifting phase, affecting a broad area around the future zone of crustal separation, was followed by a pre-oceanic rifting phase during which extensional strain was concentrated on the axial rift zone. This caused lateral graben systems to become inactive and they evolved into rift-rim basins. The transtensive phase of diffuse crustal extension is recognized in many intra-continental rifts. If controlling stress systems relax, these rifts abort and develop into palaeorifts. If controlling stress systems persist, transtensive rift systems can enter the pre-oceanic rifting stage, during which the rift zone narrows and becomes asymmetric as a consequence of simple-shear deformation at shallow crustal levels and pure shear deformation at lower crustal and mantle-lithospheric levels. Preceding crustal separation, extensional denudation of the lithospheric mantle is possible. Progressive lithospheric attenuation entails updoming of the asthenosphere and thermal doming of the rift shoulders. Their uplift provides a major clastic source for the rift basins and the lateral rift-rim basins. Their stratigraphic record provides a sensitive tool for dating the rift shoulder uplift. Asymmetric rifting leads to the formation of asymmetric continental margins, corresponding in a simple-shear model to an upper plate and a conjugate lower plate margin, as seen in the Central Atlantic passive margins of the United States and Morocco. This rifting model can be successfully applied to the analysis of the Alpine Tethys palaeo-margins (such as Rif and the Western Alps).

Haja-asutusalueiden sakokaivolietteiden kalkkistabilointi ja hyötykäyttö maataloudessa

In the sparsely populated areas of Finland there are approximately 350 000 households and 450 000 leisure time residences outside sewer networks. According to the Finnish domestic wastewater act outside sewer networks, the Finnish Government is reducing the environmental load of domestic wastewaters by the year 2017. The law is aimed at restricting the quality of sludge from domestic wastewater purification systems. The wastewater purification systems are complex systems, which often include sedimentation basins. The sedimentation basins remove most of the nutrients from the domestic wastewaters. The Finnish Government has decided that sedimentation basin sludge must be treated before reusing. One possibility is to stabilise domestic sludge with slaked lime and to reuse treated sludge in agriculture. According to this master’s thesis lime stabilisation can be done in sedimentation basins or in decanting tanks. Decanting tanks must be under 100 m3. Dosage of stabilisation is 8,5 kg/m3 of lime. If you are treading sludge that is highly hydrous, you need 13,5 kg/m3 of lime. In stabilisation lime and sludge must be thoroughly mixed. Mixed sludge must be in sedimentation basin at least two hours. If there is evidence that sludge contains salmonella or if it’s decanting tank stabilisation time is 48 hours. Sludge must be mixed at least once during the longer stabilisation time. Lime destroys Esherichia coli and enterococcus concentrations below accepted level. Lime also destroys Salmonella bacterium. After treating, sludge’s can be distributed over a field. You can safely spread lime treated domestic sludge’s about 40 m3/ha. Lime stabilisation can also be used to treat separately and collectively collected domestic wastewaters.

Palaeotectonic and palaeogeographic evolution of the western Tethys and PeriTethyan domain (IGCP Project 369)

Project No. 369 (''Comparative Evolution of PeriTethyan Rift Basins'') of the International Geological Correlation Program produced a new palaeotectonic-palaeo-geographic atlas of the western PeriTethyan domain. The atlas contains more than two hundred new maps and documents grouped in nine regional sets (Iberia, Polish Trough, Eastern European and Scythian Platforms, Moesian Platform, Levant, Arabian Platform,, Northern Africa, NE Africa-NW Arabia, Libya-Pelagian Shelf plus a set of reconstructions for the whole western Tethys. The area, considered in the atlas stretches. from west to east, from the eastern Atlantic shores to the Urals and, from north to south, from the Baltic shield to equatorial Africa; the time span covered extends from the Late. Carboniferous to the Present. The dataset, resulting from an extensive cooperation between industrial and academic sources, is accessible interactively on a CD-ROM (Stampfli et al., 2001a) and includes legend, timetable, short explanatory notes, full references and additional supporting data. This dataset provides information on the development of the Tethyan realm in space and time. In particular, the relation between the Variscan and Cimmerian cycles in the Mediterranean realm is illustrated by numerous palaeogeographic and palaeotectonic maps.

Rasvaisten ja öljyisten jätevesien biologisen puhdistuksen mallinnus

Työn kirjallisuusosassa on tarkasteltu rasvaistenjätevesien puhdistuksessa käytettyjä perinteisiä käsittelymenetelmiä ja ultrasuodatusta. Perinteisiä rasvaisten jätevesien käsittelymenetelmiä ovat muun muassalaskeutus, flotaatio, hydrosykloni, pisarakoon kasvattaminen suodatus sekä biologinen käsittely. Lisäksi happohydrolyysia voidaan soveltaa edellä mainittujen menetelmien esikäsittelynä. Perinteisten puhdistusmenetelmien käyttöä rajoittavatniiden tehottomuus emulgoituneen ja liukoisen öljyn poistossa. Tämä sekä kiristyneet päästövaatimukset ja kalvotekniikan nopea kehittyminen ovat lisänneet kiinnostusta kalvotekniikkaan. Työn soveltavassa osassa on tarkasteltu rasvojen mahdollisesti aiheuttamia ongelmia Porvoon jalostamon kemiallisessa ja biologisessa puhdistuksessa. Rasvaisia jätevesiä muodostuu biodieselin valmistuksessa, jossa rasvoja käytetään syöttöaineena. Vertailtaessa jalostamon vesilaitoksen nykyisiä olosuhteita ja rasvojen käsittelyn vaatimia olosuhteita havaitaan, että optimiolosuhteet ovat melko lähellä toisiaan ja rasvaisten jätevesien mukana tulevat fosfori-, typpi- ja COD-kuormat melko pieniä. Suurimmat mahdolliset rasvojen aiheuttamat ongelmat syntyvät aktiivilietelaitoksella, jossa kevyt pinnalle nouseva rasva nostaa mukanaan lietettä. Rasvat ja rasvahapot myös lisäävät rihmamaisten bakteerien kasvua, joiden runsas esiintyminen aiheuttaa huonosti laskeutuvaa lietettä, eli paisuntalietettä. Rasvaisten vesien aiheuttamaa kuormitusta aktiivilieteprosessiin on tarkasteltu Activated sludge Model No. 3:n ja bio-P fosforin poisto moduuliin pohjautuvan Excel-taulukkolaskentamallin avulla. Pohjana työssä on käytetty Tuomo Hillin vuonna 2002 diplomityönä tekemää taulukkolaskentamallia. Työssä on esitelty kaikki mallin kannalta oleelliset yhtälöt ja parametrit. Tämän tutkimuksen perusteella mallin käytettävyyttä rajoittaa se, että sitä ei ole kalibroitu Porvoon jalostamolle. Kalibroimattomalla mallilla voidaan saada vain suuntaa antavia tuloksia.

Physical Limnology in Lake Banyoles

The main physical long-scale processes occurring in Lake Banyoles are reviewed as a tribute to Prof. Margalef. These processesinclude the water fluxes below the surface of the lake, the behavior of the sediment in suspension in the basins, the heat fluxesat the surface and at the bottom layers, the internal seiching, the formation of a baroclinic current due to differences in coolingbetween the two lobes, the mixing dynamics, the meromictic behavior of some of the basins and the formation and dynamics of hydrothermal plumes

LWC-linjan pituushylyn hallinta

Työn tavoitteena oli saavuttaa päällystysasemilla sama tuotantotehokkuus kuin vuonna 1999, jolloin ne hankittiin. Tällöin myös määritettiin takuuarvot aseman toiminnallisista ominaisuuksista. Työtä aloitettaessa profiilien ja päällystemäärien asettuminen kesti kuitenkin huomattavasti kauemmin kuin takuuarvoissa oli määritelty. Keinoina jolla takuuarvoihin voitaisiin taas päästä, kuuluivat pastan konekiertojen kunnon tarkastus, päällystysasemien mekaanisten vikojen korjaaminen, laatusäätöjärjestelmän uudelleen virittäminen ja parhaiden työtapojen yhtenäistäminen eri vuorojen keskuudessa. Toisena tavoitteena oli luoda pituushylyn mittaus- ja raportointijärjestelmä koko tuotantolinjalle. Paperikoneelle rakennettiin automaattinen järjestelmä jolla pystyttiin seuraamaan asemien katkon jälkeistä toimintaa ja laatu virheistä syntyvää pituushylyn määrää. Jälkikäsittelyn raportointiin tehtiin sovellus johon käyttäjät pystyivät syöttämään hylättyjä paperi metrejä ja syitä niihin.

Impacts of upland open drains upon runoff generation: a numerical assessment of catchment-scale impacts

Shallow upland drains, grips, have been hypothesized as responsible for increased downstream flow magnitudes. Observations provide counterfactual evidence, often relating to the difficulty of inferring conclusions from statistical correlation and paired catchment comparisons, and the complexity of designing field experiments to test grip impacts at the catchment scale. Drainage should provide drier antecedent moisture conditions, providing more storage at the start of an event; however, grips have higher flow velocities than overland flow, thus potentially delivering flow more rapidly to the drainage network. We develop and apply a model for assessing the impacts of grips on flow hydrographs. The model was calibrated on the gripped case, and then the gripped case was compared with the intact case by removing all grips. This comparison showed that even given parameter uncertainty, the intact case had significantly higher flood peaks and lower baseflows, mirroring field observations of the hydrological response of intact peat. The simulations suggest that this is because delivery effects may not translate into catchment-scale impacts for three reasons. First, in our case, the proportions of flow path lengths that were hillslope were not changed significantly by gripping. Second, the structure of the grip network as compared with the structure of the drainage basin mitigated against grip-related increases in the concentration of runoff in the drainage network, although it did marginally reduce the mean timing of that concentration at the catchment outlet. Third, the effect of the latter upon downstream flow magnitudes can only be assessed by reference to the peak timing of other tributary basins, emphasizing that drain effects are both relative and scale dependent. However, given the importance of hillslope flow paths, we show that if upland drainage causes significant changes in surface roughness on hillslopes, then critical and important feedbacks may impact upon the speed of hydrological response. Copyright (c) 2012 John Wiley & Sons, Ltd.

Climate and human forcing of Alpine river flow

River flow in Alpine environments is likely to be highly sensitive to climate change because of the effects of warming upon snow and ice, and hence the intra-annual distribution of river runoff. It is also likely to be influenced strongly by human impacts both upon hydrology (e.g. flow abstraction) and river regulation. This paper compares the river flow and sediment flux of two Alpine drainage basins over the last 5 to 7 decades, one that is largely unimpacted by human activities, one strongly impacted by flow abstraction for hydroelectricity. The analysis shows that both river flow and sediment transport capacity are strongly dependent upon the effects of temperature and precipitation availability upon snow accumulation. As the latter tends to increase annual maximum flows, and given the non-linear form of most sediment transport laws, current warming trends may lead to increased sedimentation in Alpine rivers. However, extension to a system impacted upon by flow abstraction reveals the dominant effect that human activity can have upon river sedimentation but also how human response to sediment management has co-evolved with climate forcing to make disentangling the two very difficult.

Natural or naturalized? phylogeography suggests that the abundant sea urchin arbacia lixula Is a recent Colonizer of the Mediterranean

We present the global phylogeography of the black sea urchin Arbacia lixula, an amphi-Atlantic echinoid with potential to strongly impact shallow rocky ecosystems. Sequences of the mitochondrial cytochrome c oxidase gene of 604 specimens from 24 localities were obtained, covering most of the distribution area of the species, including the Mediterranean and both shores of the Atlantic. Genetic diversity measures, phylogeographic patterns, demographic parameters and population differentiation were analysed. We found high haplotype diversity but relatively low nucleotide diversity, with 176 haplotypes grouped within three haplogroups: one is shared between Eastern Atlantic (including Mediterranean) and Brazilian populations, the second is found in Eastern Atlantic and the Mediterranean and the third is exclusively from Brazil. Significant genetic differentiation was found between Brazilian, Eastern Atlantic and Mediterranean regions, but no differentiation was found among Mediterranean sub-basins or among Eastern Atlantic sub-regions. The star-shaped topology of the haplotype network and the unimodal mismatch distributions of Mediterranean and Eastern Atlantic samples suggest that these populations have suffered very recent demographic expansions. These expansions could be dated 94-205 kya in the Mediterranean, and 31-67 kya in the Eastern Atlantic. In contrast, Brazilian populations did not show any signature of population expansion. Our results indicate that all populations of A. lixula constitute a single species. The Brazilian populations probably diverged from an Eastern Atlantic stock. The present-day genetic structure of the species in Eastern Atlantic and the Mediterranean is shaped by very recent demographic processes. Our results support the view (backed by the lack of fossil record) that A. lixula is a recent thermophilous colonizer which spread throughout the Mediterranean during a warm period of the Pleistocene, probably during the last interglacial. Implications for the possible future impact of A. lixula on shallow Mediterranean ecosystems in the context of global warming trends must be considered.

Estructura y relleno sedimentario de la semifosa neógena de Vilanova (Garraf, Barcelona)

En el presente trabajo se aborda el estudio de una cuenca sedimentaria mediante la utilización conjunta de técnicas de cartografía geológica y datos de subsuelo, provenientes del análisis de sondeos mecánicos y de la determinación de las anomalías de la gravedad. La cuenca presenta una geometría asimétrica en forma de semigraben orientado segun la dirección regional ENE-OSO, controlado por fallas normales en dicha dirección en su límite NO, mientras que por el SE está delimitado por una discordancia. La existencia de un sistema asociado de fracturas, ortogonalmente dispuestas, complica el dispositivo anterior, resultando un basamento estructurado en bloques que configuran pequeñas subcuencas. La modelización gravimétrica de la cuenca en 3D ha permitido obtener un modelo de gran resolución para la geometria del basamento. El modelo geofísico obtenido ha sido contrastado con los datos provenientes de los sondeos...

Estructura y relleno sedimentario de la semifosa neógena de Vilanova (Garraf, Barcelona)

En el presente trabajo se aborda el estudio de una cuenca sedimentaria mediante la utilización conjunta de técnicas de cartografía geológica y datos de subsuelo, provenientes del análisis de sondeos mecánicos y de la determinación de las anomalías de la gravedad. La cuenca presenta una geometría asimétrica en forma de semigraben orientado segun la dirección regional ENE-OSO, controlado por fallas normales en dicha dirección en su límite NO, mientras que por el SE está delimitado por una discordancia. La existencia de un sistema asociado de fracturas, ortogonalmente dispuestas, complica el dispositivo anterior, resultando un basamento estructurado en bloques que configuran pequeñas subcuencas. La modelización gravimétrica de la cuenca en 3D ha permitido obtener un modelo de gran resolución para la geometria del basamento. El modelo geofísico obtenido ha sido contrastado con los datos provenientes de los sondeos...

Bioavailability of sinking organic matter in the Blanes canyon and the adjacent open slope (NW Mediterranean Sea)

Submarine canyons are sites of intense energy and material exchange between the shelf and the deep adjacent basins. To test the hypothesis that active submarine canyons represent preferential conduits of available food for the deep-sea benthos, two mooring lines were deployed at 1200 m depth from November 2008 to November 2009 inside the Blanes canyon and on the adjacent open slope (Catalan Margin, NW Mediterranean Sea). We investigated the fluxes, biochemical composition and food quality of sinking organic carbon (OC). OC fluxes in the canyon and the open slope varied among sampling periods, though not onsistently in the two sites. In particular, while in the open slope the highest OC fluxes were observed in August 2009, in the canyon the highest OC fluxes occurred in April-May 2009. For almost the entire study period, the OC fluxes in the canyon were significantly higher than those in the open slope, whereas OC contents of sinking particles collected in the open slope were consistently higher than those in the canyon. This result confirms that submarine canyons are effective conveyors of OC to the deep sea. Particles transferred to the deep sea floor through the canyons are predominantly of inorganic origin, significantly higher than that reaching the open slope at a similar water depth. Using multivariate statistical tests, two major clusters of sampling periods were identified: one in the canyon that grouped trap samples collected in December 2008, oncurrently with the occurrence of a major storm at the sea surface, and associated with increased fluxes of nutritionally available particles from the upper shelf. Another cluster grouped samples from both the canyon and the open slope collected in March 2009, concurrently with the occurrence of the seasonal phytoplankton bloom at the sea surface, and associated with increased fluxes of total phytopigments. Our results confirm the key ecological role of submarine canyons for the functioning of deep-sea ecosystems, and highlight the importance of canyons in linking episodic storms and primary production occurring at the sea surface to the deep sea floor.

Pohjavesihanke ja sen toteutus

Pohjavesihankkeen onnistunut toteutus vaatii tietoa useilta eri aloilta. Perustieto pohjavesistä, niiden muodostumisesta ja esiintymisestä, pohjavesiä koskevan lainsäädännön ja vedenottoon tarvittavien lupien tuntemus, pohjavesitutkimuksen eri vaiheiden hallitseminen ja tieto näiden vaiheiden kestoon, aikatauluun ja kustannuksiin vaikuttavista tekijöistä ovat kaikki onnistuneen hankkeen edellytyksiä. Tässä diplomityössä selvitetään pohjavesihankkeen eri vaiheet sekä niiden sisältö ja tarvittavat toimenpiteet vesihuoltolaitoksen kannalta.Työssä tarkastellaan yleisesti kunnallista vesihuoltoa Suomessa ja Suomen pohjavesioloja. Lisäksi tarkastellaan pohjavesiä koskevaa lainsäädäntöä sekä pohjavesialueiden kartoituksen ja luokituksen nykytilannetta. Työssä käsitellään esiintymäkohtaisen pohjavesitutkimuksen eri vaiheet menetelmineen. Pohjavesitutkimusten ja pohjavedenoton vaatimat luvat käydään läpi.Pohjavesihanke on jaettu osiin, joiden kestoa ja niihin vaikuttavia tekijöitä tarkastellaan. Lisäksi pohjavesihankkeesta on tehty esimerkkiaikataulu, jossa eri työvaiheiden vaatimat ajat esitetään suhteessa toisiinsa. Hankkeen kustannukset on jaettu henkilöstö-, materiaali- ja muihin kustannuksiin. Näiden rakenne eri työvaiheissa on selvitetty.Joensuun Veden Paavonlammen alueella Kiihtelysvaaran kunnassa tekemän esimerkkihankkeen avulla havainnollistetaan sitä, millä tavoin käyttöön otettavan pohjavesialueen ominaisuudet sekä käytettävissä oleva työvoima ja kalusto vaikuttavat kustannuksiin, aikatauluun ja eri tutkimusvaiheiden tarpeellisuuteen.Pohjavesihanketta aloitettaessa ja sen aikana on kiinnitettävä erityisesti huomiota avoimeen tiedottamiseen vaikutusalueen asukkaille ja maanomistajille. Keskeistä työn edetessä on ottaa huomioon se, että pohjavesihankkeen toteutus etenee vaiheittain aikaisempien tulosten perusteella.

Biologisen jätevedenpuhdistuksen ilmastuksen tehostaminen

Työssä tutkittiin, mikä on kustannustehokkain tapa lisätä ilmastuskapasiteettia ja selvitettiin, saostaako vesilaitokselta flotaatioaltaasta poistettava ferrisulfaattisakka jäteveden fosforia esiselkeyttimessä. Työssä määritettiin teoreettinen hapentarve ilmastusaltaassa maksimikuormituksen aikana ja hapensiirtonopeus jäteveteen olemassa olevalla laitteistolla. Hapensiirtonopeuden funktion korjauskertoimet  ja  sekä kokonaishapensiirtokerroin määritettiin laboratorio-olosuhteissa. Lisäksi laskettiin kuinka paljon nykyisten ilmastimien kautta saadaan happea jäteveteen liukenemaan ja verrattiin tätä lukua teoreettiseen hapentarpeeseen. Jälkimmäistä menettelytapaa käyttäen arvioitiin lisähapen tarve. Tulokseksi saatiin, että maksimi BOD-kuormituksen aikana happea tarvitsee saada jäteveteen liuotettua 5200 m³/d lisää. Ilmastuskapasiteetin lisäyksen kustannuslaskelmassa verrattiin neljää vaihtoehtoa: puhdasta happea liuotettuna happimattojen kautta tai OKI-ilmastimen kautta, onsite-happilaitoksen puhdasta happea liuotettuna OKI-ilmastimen kautta tai ilman happea liuotettuna jäteveteen EDI-ilmastimien kautta. Laskelmat osoittivat uusien EDI-ilmastimien hankinnan olevan edullisin vaihtoehto pitkällä aikavälillä. Vaikka EDI-ilmastimien investointikustannukset ovat korkeat, tulevat ne käyttökustannuksiltaan kaikkein edullisimmaksi. Vesilaitokselta tulevan rautasuolasakan fosforia saostavaa vaikutusta tutkittiin laboratoriossa astiakokein. Näytteet otettiin vesilaitokselta jätevesilaitokselle menevästä rautasuolasakasta sekä esiselkeyttimen kirkasteesta. Näitä eri suhteissa keskenään sekoittamalla saatiin selville, että rautasuolasakka ja sakan mukana tuleva reagoimaton rautasuola saostavat liukoista ja kokonaisfosforia esiselkeytyksessä.